怎样把一组数分成两组，使得每组的和为给定的值a,b?
DP:
表示前x个发票，是否有子集组成y的金额。
, v_x是第x个发票的金额。算到 【怎样把一组数分成两组，使得每组的和为给定的值a,b?】
■网友
谢邀但是这个问题没有简单的解法，这是一个NP问题
■网友
如果不考虑效率（O(n*S)），可以用类似背包的DP，如下（python）def f(v, i, S, memo): if i \u0026gt;= len(v): return 1 if S == 0 else 0 if (i, S) not in memo: # \u0026lt;-- Check if value has not been calculated. count = f(v, i + 1, S, memo) count += f(v, i + 1, S - v, memo) memo = count # \u0026lt;-- Memoize calculated result. return memo # \u0026lt;-- Return memoized value.def g(v, S, memo): subset = for i, x in enumerate(v): # Check if there is still a solution if we include v if f(v, i + 1, S - x, memo) \u0026gt; 0: subset.append(x) S -= x return subsetv = sum = int(input())memo = dict()if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")else: print(g(v, sum, memo))
推荐阅读
- 聪明人养花，这3种“花”怎样也要养一盆，每年能省不少医药费
- 互联网怎样解决“家政服务上门速度慢”的问题
- 怎样看待从1月8号起，QQ钱包开始提现收费
- 银行it人怎样转型
- 汽车|冬天怎样让车内温度快速升高？座椅加热的最佳使用方式二，外循环的作用总结
- 怎样进入通信行业
- 怎样评价扶他柠檬茶的小说《云养汉》的结尾
- 怎样成为一名合格的Python程序员?
- 怎样评价华为、诺基亚、中兴中标中国移动高端路由交换设备扩容集采
- 怎样评价类似前橙会、百老汇、南极圈这样类型的离职帮抱团，对企业的积极意义和消极意义