给出一个整数和阈值T的集合,将该集合分成总和> = T的尽可能多的组。
剩余的整数(其总和 约束: 多项式时间内是否有针对此问题的算法? 例如,给定 选择[25,25,25,50,50,50,10]
和阈值T = 70
,它应该返回:[25,50]
[25,50]
[25,50]
Remaining: [10]
[25,25,25]
作为组之一将使得可以仅再形成一个组[50,50]
,其余值为[50,10]
。两组不是最佳的组数量,这就是为什么此解决方案不正确的原因。
没有多项式时间算法,因为它在特殊情况下包含np-complete Partition problem。