背包问题：袋子重量可变

Question

考虑一份重量清单和一份重量可变的行李清单。我需要一种算法来找到存储所有重量所需的最小袋子数量。

简单地按降序排序是行不通的。考虑这个例子：

weights = [8,7,4,4]
bags = [16,7,5,5]

如果我们开始按降序插入权重，我们最终会得到：

1st bag (capacity of 16): [8,7]
2nd bag (capacity of 7): [4]
3rd bag (capacity of 5): [4]

而最优解是：

1st bag: [8,4,4]
2nd bag: [7]

Answer 1

这个问题可以被视为装箱问题的变体。

装箱是一个优化问题，其中不同尺寸的物品必须装入有限数量的箱子或容器中，每个箱子或容器具有固定的给定容量，以最小化所使用的箱子数量的方式。

这个问题是 NP 难题，并且已经针对它提出了各种（指数时间）精确算法（here）。解决您所描述的问题实例（以精确的方式）的一种简单方法是将其建模为整数线性程序：

% weights = [8,7,4,4]
% bags = [16,7,5,5]   
         
array[1..4,1..4] of  var 0..1: x;
array[1..4] of  var 0..1: y;

constraint x[1,1]+x[1,2]+x[1,3]+x[1,4] = 1;
constraint x[2,1]+x[2,2]+x[2,3]+x[2,4] = 1;
constraint x[3,1]+x[3,2]+x[3,3]+x[3,4] = 1;
constraint x[4,1]+x[4,2]+x[4,3]+x[4,4] = 1;
constraint 8*x[1,1]+7*x[2,1]+4*x[3,1]+4*x[4,1] <= 16 * y[1];
constraint 8*x[1,2]+7*x[2,2]+4*x[3,2]+4*x[4,2] <= 7 * y[2];
constraint 8*x[1,3]+7*x[2,3]+4*x[3,3]+4*x[4,3] <= 5 * y[3];
constraint 8*x[1,4]+7*x[2,4]+4*x[3,4]+4*x[4,4] <= 5 * y[4];

solve minimize y[1] + y[2] + y[3] + y[4];

前四个约束表示每个项目必须恰好放置在一个箱子中，后四个约束实际上是容量约束。我通过 MiniZinc 中的 Gecode 求解器求解了模型。一种最佳解决方案是：

x = array2d(1..4, 1..4, [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]);
y = array1d(1..4, [1, 1, 0, 0]);

解决方案表明我们必须将重量为 8 的物品、重量为 4 的物品放入第一个 bin 中，将重量为 7 的物品放入第二个 bin 中。