recursion - 可以使用指定重量的背包问题

Question

我有一个背包问题，指定的背包重量和重量计数。

我需要一种算法，当背包容量为 C、所需的重量计数为 N 并且有一个重量列表时，将重量打包到背包中。权重排序无关紧要。如果算法是递归的，那将是最好的。

例如：
我有一个背包女巫只能装 3 个重量，而他们的重量必须是 10，而我有这些重量：9、8、7、2、1。正确（也是唯一）答案是 7、2、1。

如果有人编写伪代码最好，但如果它是任何常见的编程语言都可以。

PS 任何提示也值得赞赏:)

[编辑]我需要一个算法，它给出的答案正好是 N 权重计数，它的权重正好是 C。

Answer 1

这就是 0-1 背包问题，可以在伪多项式时间内使用动态规划来解决。

有关如何使用动态规划解决问题的说明，请参阅Wikipedia 的背包问题文章。

有关演练和伪代码，请参阅这些 CS 讲座幻灯片。

Answer 2

http://en.wikipedia.org/wiki/Knapsack_problem应该可以帮助你。他们也有算法的伪代码。