文章目錄

如果有n个对象, 它们的计量单位各为k1, k2, …, kn; 现在有一个可以容纳K单位的背包, 请写一个程序, 找出有没有办法在1, 2, …, n中选P个元素出来, 使得计量单位的总和为K, 可以刚好把背包装满。这就是有名的背包问题(Knapsack Problem)

说明:以计量单位分别是1, 2, 4, 7, 10, 12, 13, 15, 17这9个对象来看好了, 若背包的容量是27, 可以取4,10与13, 因为4 + 10 + 13 = 27; 但也可以取2, 12, 13, 因为27 = 2 + 12 + 13; 更可以取10与17, 因为27 = 10 + 17;当然还有其他的可能解答。不过,这个题目却是不一定有解的。例如, 若对象的计量单位是1, 5, 10, 15, 20; 而背包是14, 物件中比14小的有1, 5, 10, 无论如何选择, 都不可能加出一个14来的。

就像上一题找零钱的问题一样, 可以用动态规划的技巧来解这个问题, 不过会复杂, 但基本道理是完全相同的. 这里要求有解的时候,找出一个解。

解答见knapsack.py

打赏作者

文章目錄