1

私は思考の問題に遭遇し、ただイライラしています。私は動的計画法を使用して、ナップザック問題の実用的なアルゴリズムを持っています。

  • 最大荷重
  • アイテム（重量）

アルゴリズムは、それらのアイテムを使用してナップザックの最適な充填を計算します。しかし、今は最小限のアイテムを使用して完全に埋める必要がありますが、各アイテムの量は無制限です。（これらのアイテムには重量があるため、常に完了することができます）。{1; w1; w2; ...}

これを「クラシック」アルゴリズムにどのように適合させるのですか?

ありがとう

4

1 に答える 1

3

させて

  • M = 満たす必要がある量
  • w[] = 重みの配列
  • dp[] = 最適な塗りつぶしの配列 (dp[i] には、重み i を満たすために必要なアイテムの最小数が含まれます)。

 initialize the dp array with INFINITY, dp[0] = 0;
 for(i = 0;i<size of w;i++) {
    for(j = 1;j<=M;j++) {
       if(j-w[i] >= 0) {
          dp[j] = min(dp[j], dp[j-w[i]]+1);
       }
    }
 }

 final solution is the value of dp[M];
于 2011-11-01T08:58:42.173 に答える