我有一个背包问题,有指定的背包重量和重量计数能力。
我需要一种算法,当背包容量为C,所需权重计数为N,并且有一个权重列表时,将权重打包到背包。权数的排序并不重要。如果算法是递归的,这将是最好的。
例如:
我有背包巫婆只能装3个重量,他们必须有10个重量,我有这些重量: 9,8,7,2,1。正确的答案是7,2,1。
最好是有人写伪代码,但如果它是任何一种常见的编程语言,那就好了。
P.S.任何值得赞赏的提示:)
编辑需要给出答案的算法,精确的N个权重计数,其中的权重精确C。
发布于 2011-03-27 19:55:22
这是一个0-1背包问题,它可以在伪多项式时间内用动态规划来求解.
有关如何使用动态编程解决问题的说明,请参见维基百科背包问题文章。
有关演练和伪代码,请参见这些CS演讲幻灯片。
发布于 2011-03-27 19:54:49
问题应该能帮你。他们也有算法的伪码。
https://stackoverflow.com/questions/5451873
复制相似问题