求在一定极限下的最大子集

Question

给定一个实数列表A = [a1, a2, a3,..., an]和一个实数x，是否存在一个多项式时间算法使A的子集b使得:

• sum(b) <= x;和
• 不存在A的另一个子集c，使得sum(c) <= x and sum(b) < sum(c) ?

Answer 1

我99%肯定这是不可能的。这听起来像是对背包问题的重述——或者，至少，背包问题可以简化为这样。除非P=NP，否则你就没那么幸运了。