C++で0/1ナップザックでアイテムを印刷する

n個のアイテムの重みと値を指定します。タスクは、容量Wのナップザックに次の重みと値の0/1ナップザックに従ってアイテムを印刷し、ナップザックの最大合計値を取得することです。

0/1ナップザックとは何ですか？

ナップザックは、固定サイズの鞄や、ある程度の重さを扱える鞄のようなものです。ナップザックに含まれる各アイテムには、ある程度の価値（利益）と重みがあります。ナップザックが保持できる総重量に応じて最大の利益が得られる重量を追加する必要があります。

つまり、ナップザックが保持できるバッグの重量、値（利益）、および総重量があるので、0/1ナップザックでは、含まれるアイテムに1と0を指定します。ここで、0は可能なアイテムを表します。バッグに入れてください。1はナップザックに入れることができるアイテムです。

簡単な例を使って理解しましょう-

Let us assume val[] = {1, 2, 5, 6}//value or profit
wt[] = {2, 3, 4, 5}//weight
W = 8//Capacity

そのナップザックテーブルは-

knapsack.jpg

ナップザックテーブルは、次の式を使用して埋めることができます-

K [i、w] =max⁡{K[i-1、w]、K [i-1、w-wt [i]] + Val [i]}

バックトラッキングアプローチを使用してテーブルを解決する

これで、すべてのアイテムの利益と、特定のアイテムを追加した後に取得できる最大ウェイト内の利益の最大値のデータが得られました。

• k [n] [w]からバックトラックを開始します。ここで、k[n][w]は8です。
• 青い矢印が黒い矢印が行くところまでずっと上に案内するので、上方向に進みます。つまり、8は4行目だけなので、4番目のオブジェクトを含めます。これは、4番目のアイテムを追加した後に最大の利益を得たことを意味します。
• 合計利益8を差し引いて、4番目の項目を追加して得られた利益を差し引きます。つまり、6を差し引くと2になります。
• テーブルをバックトラックして、最大利益として2を獲得したときに探します。 2番目のアイテムを追加したときに取得しました
• したがって、バッグを効率的に満たし、最大の利益を達成するために、ナップザックに2番目と4番目のアイテムを追加します。

例

Input: val[] = {60, 100, 120}
wt[] = {10, 20, 30}
w = 50
Output: 220 //max value
30 20 //weights
Explanation: to reach till the maximum weight i.e. 50 we will add two weights value,
30 whose value is 120 and 20 whose value is 100

Input: val[] = {10, 40, 50}
wt[] = {2, 4, 5}
w = 6
Output: 50
4 2
Explanation: to reach till the maximum weight i.e. 6 we will add two weights value, 4
whose value is 40 and 2 whose value is 10.

アルゴリズム

Start
Step 1-> In function max(int a, int b)
   Return (a > b) ? a : b
Step 2-> In function printknapSack(int W, int wt[], int val[], int n)
   Decalare i, w, K[n + 1][W + 1]
   Loop For i = 0 and i <= n and i++
      Loop For w = 0 and w <= W and w++
         If i == 0 || w == 0 then,
            Set K[i][w] = 0
         Else If wt[i - 1] <= w then,
            Set K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
         Else
            Set K[i][w] = K[i - 1][w]
            Set res = K[n][W]
            Print res
            Set w = W
         Loop For i = n and i > 0 && res > 0 and i--
            If res == K[i - 1][w] then,
               Continue
            Else {
               Print wt[i - 1])
               Set res = res - val[i - 1]
               Set w = w - wt[i - 1]
Step 3-> In function int main()
   Set val[] = { 50, 120, 70 }
   Set wt[] = { 10, 20, 30 }
   Set W = 50
   Set n = sizeof(val) / sizeof(val[0])
   Call function printknapSack(W, wt, val, n)
Stop

例

#include <bits/stdc++.h>
int max(int a, int b) { return (a > b) ? a : b; }
// Prints the items which are put in a knapsack of capacity W
void printknapSack(int W, int wt[], int val[], int n) {
   int i, w;
   int K[n + 1][W + 1];
   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++) {
      for (w = 0; w <= W; w++) {
         if (i == 0 || w == 0)
            K[i][w] = 0;
         else if (wt[i - 1] <= w)
            K[i][w] = max(val[i - 1] +
            K[i - 1][w - wt[i - 1]], K[i - 1][w]);
         else
            K[i][w] = K[i - 1][w];
      }
   }
   // stores the result of Knapsack
   int res = K[n][W];
   printf("maximum value=%d\n", res);
   w = W;
   printf("weights included\n");
   for (i = n; i > 0 && res > 0; i--) {
      if (res == K[i - 1][w])
         continue;
      else {
         printf("%d ", wt[i - 1]);
         res = res - val[i - 1];
         w = w - wt[i - 1];
      }
   }
}
// main code
int main() {
   int val[] = { 50, 120, 70 };
   int wt[] = { 10, 20, 30 };
   int W = 50;
   int n = sizeof(val) / sizeof(val[0]);
   printknapSack(W, wt, val, n);
   return 0;
}

出力

maximum value=190
weights included
30 20