在阵列中受约束的最大总和

Question

如何找到最大总和< = K在没有其他约束的阵列（元件不必是连续的或不连续的）

Answer 1

这可以使用0/1 knapsack problem的动态规划算法解决，元素值设置为等于元素权重。

Answer 2

这是一个subset sum problem的变化。

这个问题是NP-Complete，所以没有已知的多项式解决方案。
但是，如果您的列表包含相对较小的整数，there is an efficient Dynamic Programming pseudo-polynomial solution。

其他替代方法是检查所有2^n个可能的子集并检查其中的最佳值。