首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >可以使用指定重量数的背包问题。

可以使用指定重量数的背包问题。
EN

Stack Overflow用户
提问于 2011-03-27 19:44:51
回答 2查看 2.8K关注 0票数 1

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

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

例如:

我有背包巫婆只能装3个重量,他们必须有10个重量,我有这些重量: 9,8,7,2,1。正确的答案是7,2,1。

最好是有人写伪代码,但如果它是任何一种常见的编程语言,那就好了。

P.S.任何值得赞赏的提示:)

编辑需要给出答案的算法,精确的N个权重计数,其中的权重精确C。

EN

回答 2

Stack Overflow用户

发布于 2011-03-27 19:55:22

这是一个0-1背包问题,它可以在伪多项式时间内用动态规划来求解.

有关如何使用动态编程解决问题的说明,请参见维基百科背包问题文章

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

票数 1
EN

Stack Overflow用户

发布于 2011-03-27 19:54:49

问题应该能帮你。他们也有算法的伪码。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/5451873

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档