c# - 确定最佳组合的算法 - 装箱

Question

给定一组项目，每个项目都有一个值，确定要包含在集合中的每个项目的数量，以使总值小于或等于给定限制，并且总值尽可能大。

例子:

Product A = 4
Product B = 3
Product C = 2
Product D = 5

If Total Capacity = 10.5 , then the combination of B,C,D will be selected.
If Total Capacity = 12.5 , then the combination of A,B,D will be selected.
If Total Capacity = 17 , then the combination of A,B,C,D will be selected.

我正在寻找一种算法(如背包或装箱)来确定组合。任何帮助表示赞赏。

Answer 1

你说这是“像背包”。据我所知，这是 bounded knapsack problem 的特例称为 0-1 背包问题。

它是 NP 完全的。

您可以尝试多种方法来解决它。有关一种方法，请参阅此相关问题:

• Writing Simulated Annealing algorithm for 0-1 knapsack in C#

如果您只有四个项目，那么只需测试所有可能性就可以满足大多数目的。