1

问题陈述：您有 n1 件尺寸为 s1 的物品，n2 件尺寸为 s2 的物品，以及 n3 件尺寸为 s3 的物品。您希望将所有这些物品装入每个容量为 C 的箱子中，以使使用的箱子总数最小化。

我的解决方案：

Bin(C,N1,N2,N3) = max{Bin(C-N1,N1-1,N2,N3)+N1 if N1<=C and N1>0,
                      Bin(C-N2,N1,N2-1,N3)+N2 if N2<=C and N2>0,
                      Bin(C-N3,N1,N2,N3-1)+N3 if N3<=C and N3>0,
                      0 otherwise}

上述解决方案仅有效地填充单个箱。有人可以建议如何修改上述关系，以便我有效地获得用于包装物品的总箱吗？

4

1 回答 1

0

问题 你有 n1 件大小为 s1 的物品和 n2 件大小为 s2 的物品。您必须将所有这些物品打包到每个容量 C 的箱子中，以使使用的箱子总数最小化。为这种包装设计一个多项式时间算法。

这是我对这个问题的解决方案，它与您所要求的非常相似。

DP方法 假设Bin(i, j)给出使用的最小bin总数，那么Bin(i, j) = min{Bin(i′, j′) + Bin(i - i′,j - j′)}其中 i + j > i′ + j′ > 0。将有 n^2 - 2 个不同的 (i′,j′) 组合和一对 (n1,n2) 组合。所以复杂度约为 O(n^2)。

复杂度 O(n^2)

示例：设 s1 = 3，n1 = 2，s2 = 2，n2 = 2，C = 4。找到所需的最小 bin，即 b。

<pre>
i j b
- - -
0 1 1
0 2 2
1 0 1
1 1 1
1 2 2
2 0 2
2 1 3
2 2 3  -> (n1,n2) pair
</pre>

如您所见，需要 3 个垃圾箱。

<pre>
Note that Bin(2,2) = min{
  Bin(2,1) + Bin(0,1), 
  Bin(2,0) + Bin(0,2),
  Bin(1,2) + Bin(1,0),
  Bin(1,1) + Bin(1,1)} 
= min{3, 4} 
= 3
</pre>
于 2016-06-17T14:33:29.240 回答