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

输入:糖果的袋数和各袋中糖果的数量;

输出:平分下来的糖果数量,以及两个人分别分到的各袋中糖果的数量,如果无法平分,则直接输出-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)

技术
今日推荐
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信