1

問題文: サイズ s1 のアイテムが n1 個、サイズ s2 のアイテムが n2 個、サイズ s3 のアイテムが n3 個あります。使用されるビンの総数が最小になるように、これらすべてのアイテムをそれぞれ容量 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

問題 サイズ s1 のアイテムが n1 個あり、サイズ s2 のアイテムが n2 個あります。使用するビンの総数が最小限になるように、これらすべてのアイテムをそれぞれ容量 C のビンに詰める必要があります。このようなパッケージングのための多項式時間アルゴリズムを設計します。

これがこの問題に対する私の解決策であり、あなたが求めているものと非常に似ています。

DP 法 Bin(i, j) が使用されるビンの最小総数を与えると仮定すると、Bin(i, j) = min{Bin(i′, j′) + Bin(i − i′,j − j′)}ここで、i + j > i′ + j′ > 0. n^2 − 2 個の異なる (i′,j′) の組み合わせと、1 組の (n1,n2) の組み合わせがあります。したがって、複雑さは約 O(n^2) です。

複雑さ O(n^2)

例: s1 = 3、n1 = 2、s2 = 2、n2 = 2、C = 4 とします。必要な最小ビン、つまり 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 に答える