可以使用指定重量个数的背包问题
我有一个背包问题，指定背包的重量和重量计数容量。
我需要一种算法，当背包容量为C，所需重量计数为N并且有一个重量列表时，将重量打包到背包中。权重的排序并不重要。如果算法是递归的那就最好了。
例如：
我的背包女巫只能容纳 3 个重量，它们必须重 10 个，我有这些重量：9、8、7、2、1。正确（也是唯一）的答案是 7、2、1。
最好是有人编写伪代码，但如果是任何常见的编程语言都可以。
PS 任何提示也值得赞赏:)
[编辑]我需要算法精确给出 N 个权重计数的答案，其中 N 个权重计数的权重恰好为 C。
I have a knapsack problem with specified knapsack capacity for weight and weights count.
I need an algorithm that packs weights to knapsack when knapsack capacity is C, needed weights count is N and there is a list of weights. Sorting of weights doesn't matter. It would be best if algorithm is recursive.
For example:
I have knapsack witch can hold only 3 weights and they have to weight 10 and I have these weights: 9, 8, 7, 2, 1. The correct (and only) answer is 7, 2, 1.
It would be best if someone write pseudocode, but its ok if its any of the common programing languages.
P.S. Any tips its appreciated as well :)
[EDIT]I need algorithm that gives answer with exactly the N weights count which weights exactly C.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这就是 0-1 背包问题，可以在伪多项式时间内使用动态规划来解决。
有关如何使用动态规划解决问题的说明，请参阅维基百科的背包问题文章。
请参阅这些 CS 讲座幻灯片进行演示-通过和伪代码。
This is the 0-1 knapsack problem, which can be solved using dynamic programming in pseudo-plynomial time.
See Wikipedia's knapsack problem article for instructions on how to solve the problem using dynamic programming.
See these CS lecture slides for a walk-through and pseudocode.
http://en.wikipedia.org/wiki/Knapsack_problem 应该对你有帮助。他们也有算法的伪代码。
http://en.wikipedia.org/wiki/Knapsack_problem should help you. They have pseudocode for algorithms as well.