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

Question

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

例子：

产品 A = 4
产品 B = 3
产品 C = 2
产品 D = 5

如果 Total Capacity = 10.5 ，则将选择 B,C,D 的组合。
如果 Total Capacity = 12.5 ，则将选择 A,B,D 的组合。
如果 Total Capacity = 17 ，则将选择 A,B,C,D 的组合。

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

Answer 1

你说这是“像背包一样”。据我所知，这是有界背包问题的一个特例，称为 0-1 背包问题。

它是NP完全的。

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

• 用 C# 编写 0-1 背包的模拟退火算法

如果您只有四个项目，那么仅测试所有可能性对于大多数用途来说应该足够快。