确定最佳组合的算法 - Bin Packing

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

你说这就像"背包".据我所知,这是一个特殊的有界背包问题,称为0-1背包问题.

它是NP完全的.

有很多方法可以尝试解决它.有关一种方法,请参阅此相关问题:

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

如果您只有四个项目,那么只测试所有可能性应该足够快以满足大多数目的.