华为OD机试真题：分糖果-均分【2022 Q1 Q2 |200分】

题目描述： 现有几袋糖果，老师要将糖果分给小张和小王两个同学，每一袋都有一定数量的糖果，每袋糖果只能全部分给他们其中一人，要求最终两人分得糖果的数量相同。

输入：糖果的袋数和各袋中糖果的数量；

输出：平分下来的糖果数量，以及两个人分别分到的各袋中糖果的数量，如果无法平分，则直接输出-1

示例1： 1.输入： 5 2 6 5 4 7 输出： 12 2 4 6 5 7 2.输入： 4 1 2 3 5 输出： -1

#解题想法：再背包问题的基础上，增加一个记录当前节点的满足条件的list




m=5
l=[2,6,5,4,7]

su=sum(l)
if su%2==1:
    print(-1)
else:
    t=int(su/2)

    dp=[[False]*(t+1) for _ in range(0,len(l))]
    print(dp)
    dp[0][l[0]]=True
    for i in range(0,len(l)):
        dp[i][0]=True

    dp2 = [[""] * (t + 1) for _ in range(0, len(l))]
    print(dp2)
    dp2[0][l[0]] = str(l[0])


    for i in range(1,len(l)):
        for j in range(1,t+1):
            if j>l[i]:
                dp[i][j]=dp[i-1][j]|dp[i-1][j-l[i]]

                if dp[i-1][j]:
                    dp2[i][j]=dp2[i-1][j]
                if dp[i-1][j-l[i]]:
                    dp2[i][j] =dp2[i-1][j-l[i]]+str(l[i])

            else:
                dp[i][j]=dp[i-1][j]
                dp2[i][j] = dp2[i - 1][j]
    print(dp)

    if dp[-1][-1]:

        tmp=list(map(int,list(dp2[-1][-1])))

        tmp2=list(set(l)-set(tmp))

        tmp.sort()

        tmp2.sort()

        for i in tmp:
            print(i,end=" ")
            
        print()

        for i in tmp2:
            print(i,end=" ")


    else:
        print(-1)