1

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

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

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

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

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

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

4

2 回答 2

1

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

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

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

于 2011-03-27T19:55:22.820 回答
0

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

于 2011-03-27T19:54:49.747 回答