背包问题的变体
我有“n”个金额（非负整数）。我的要求是确定一组最佳金额，使组合总和小于或等于给定的固定限制，并且总数尽可能大。最佳集合中可以包含的金额数量没有限制。
举例来说：金额为 143,2054,546,3564,1402，给定的限制为 5000。
根据我的理解，背包问题的每个项目有 2 个属性（重量和价值）。但上述问题只有一个属性（金额）。我希望这会让事情变得更简单？ :)
有人可以帮我解决这个问题的算法或源代码吗？
I have 'n' number of amounts (non-negative integers). My requirement is to determine an optimal set of amounts so that the sum of the combination is less than or equal to a given fixed limit and the total is as large as possible. There is no limit to the number of amounts that can be included in the optimal set.
for sake of example: amounts are 143,2054,546,3564,1402 and the given limit is 5000.
As per my understanding the knapsack problem has 2 attributes for each item (weight and value). But the problem stated above has only one attribute (amount). I hope that would make things simpler? :)
Can someone please help me with the algorithm or source code for solving this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这仍然是一个 NP 难题，但是如果您想要（或必须）做类似的事情，也许这个主题可以帮助您一点：
从数字列表中查找两个或多个数字，这些数字加起来达到给定的金额
，其中 i 像这样解决了并修改了NikiC它 更快。唯一的区别：这是关于获得准确的金额，而不是“尽可能接近”，但这只是代码中的一些小变化（并且您必须将其翻译成您正在使用的语言）。
看一下我的代码中的注释，以了解我想要做什么，简而言之：
，对所有可能的解决方案进行排序，以获得使用最少部分的解决方案，因此您必须更改：
this is still an NP-hard problem, but if you want to (or have to) to do something like that, maybe this topic helps you out a bit:
find two or more numbers from a list of numbers that add up towards a given amount
where i solved it like this and NikiC modified it to be faster. only difference: that one was about getting the exact amount, not "as close as possible", but that would be only some small changes in code (and you'll have to translate it into the language you're using).
take a look at the comments in my code to understand what i'm trying to do, wich is, in short form:
so you'll have to change:
这本书"背包问题” 作者：Hans Kellerer、Ulrich Pferschy 和 David Pisinger，将其称为子集和问题并用一整章（第 4 章）专门讨论它。本章非常全面，涵盖了算法和计算结果。
尽管这个问题是背包问题的特例，但它仍然是 NP 困难的。
The book "Knapsack Problems" By Hans Kellerer, Ulrich Pferschy and David Pisinger calls this The Subset Sum Problem and dedicates an entire chapter (Ch 4) to it. The chapter is very comprehensive and covers algorithms as well as computational results.
Even though this problem is a special case of the knapsack problem, it is still NP-hard.