0-1 揹包問題

在本教程的前面，我們討論了使用貪心演算法解決分數揹包問題。結果表明，貪心演算法可以為分數揹包問題提供最優解。但是，本章將介紹使用動態規劃方法解決 0-1 揹包問題及其分析。

與分數揹包不同，物品總是完整地儲存，而不使用其小數部分。要麼將物品新增到揹包中，要麼不新增。因此，此方法被稱為0-1 揹包問題。

因此，在 0-1 揹包問題中，x_i 的值可以是0 或1，其他約束條件保持不變。

0-1 揹包問題不能用貪心演算法解決。貪心演算法不能保證此方法中的最優解。在許多情況下，貪心演算法可能會給出最優解。

0-1 揹包演算法

問題陳述 - 小偷正在搶劫一家商店，他最多可以將W 重量的物品放入他的揹包中。有n 件物品，第 i 件物品的重量為 wi，選擇此物品的利潤為pi。小偷應該拿哪些物品？

令 i 為最優解S（價值為W 元）中編號最高的物品。那麼S’ = S − {i} 是W – w_i 元的最優解，而解 S 的值為 V_i 加上子問題的解。

我們可以用以下公式表達這一事實：定義c[i, w] 為物品1,2, … , i 和最大重量w 的解。

該演算法接收以下輸入

• 最大重量W

• 物品數量n

• 兩個序列v = <v1, v2, …, vn> 和 w = <w1, w2, …, wn>

可以從表中推匯出要攜帶的物品集，從c[n, w] 開始，並向後追溯最優值來自哪裡。

如果c[i, w] = c[i-1, w]，則物品 i 不屬於解的一部分，我們繼續使用c[i-1, w] 進行追溯。否則，物品 i 是解的一部分，我們繼續使用c [i-1, w-W] 進行追溯。

Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
   c[0, w] = 0
for i = 1 to n do
   c[i, 0] = 0
   for w = 1 to W do
      if wi ≤ w then
         if vi + c[i-1, w-wi] then
            c[i, w] = vi + c[i-1, w-wi]
         else c[i, w] = c[i-1, w]
      else
         c[i, w] = c[i-1, w]

以下示例將證明我們的陳述。

示例

讓我們考慮一下揹包的容量為 W = 8，物品如以下表格所示。

解決方案

使用 0-1 揹包的貪心演算法，儲存在揹包中的重量將是 A+B = 4，最大利潤為 2 + 4 = 6。但是，該解決方案將不是最優解決方案。

因此，必須採用動態規劃來解決 0-1 揹包問題。

步驟 1

構造一個鄰接表，揹包的最大重量作為行，物品及其相應的重量和利潤作為列。

表中儲存的值是物品的累積利潤，這些物品的重量不超過揹包的最大重量（每行的指定值）

因此，我們在第 0 行和第 0 列中新增零，因為如果物品的重量為 0，則它不重；如果揹包的最大重量為 0，則無法將任何物品新增到揹包中。

其餘的值將填充與每列中可以儲存在揹包中的物品和重量相關的最大可實現利潤。

儲存利潤值的公式為 -

$$c\left [ i,w \right ]=max\left\{c\left [ i-1,w-w\left [ i \right ] \right ]+P\left [ i \right ] \right\}$$

透過使用該公式計算所有值，獲得的表格將為 -

要查詢要新增到揹包中的物品，請從表中識別最大利潤並識別構成該利潤的物品，在本例中，為 {1, 7}。

最優解是 {1, 7}，最大利潤為 12。

分析

該演算法需要 Ɵ(n.w) 時間，因為表 c 有 (n+1).(w+1) 個條目，其中每個條目需要 Ɵ(1) 時間來計算。

實現

以下是使用動態規劃方法實現 0-1 揹包演算法的最終程式碼。

#include <stdio.h>
#include <string.h>
int findMax(int n1, int n2){
   if(n1>n2) {
      return n1;
   } else {
      return n2;
   }
}
int knapsack(int W, int wt[], int val[], int n){
   int K[n+1][W+1];
   for(int i = 0; i<=n; i++) {
      for(int w = 0; w<=W; w++) {
         if(i == 0 || w == 0) {
            K[i][w] = 0;
         } else if(wt[i-1] <= w) {
            K[i][w] = findMax(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
         } else {
            K[i][w] = K[i-1][w];
         }
      }
   }
   return K[n][W];
}
int main(){
   int val[5] = {70, 20, 50};
   int wt[5] = {11, 12, 13};
   int W = 30;
   int len = sizeof val / sizeof val[0];
   printf("Maximum Profit achieved with this knapsack: %d", knapsack(W, wt, val, len));
}

Maximum Profit achieved with this knapsack: 120

#include <bits/stdc++.h>
using namespace std;
int max(int a, int b){
   return (a > b) ? a : b;
}
int knapSack(int W, int wt[], int val[], int n){
   int i, w;
   vector<vector<int>> K(n + 1, vector<int>(W + 1));
   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];
      }
   }
   return K[n][W];
}
int main(){
   int val[] = { 70, 20, 50 };
   int wt[] = { 11, 12, 13 };
   int W = 30;
   int n = sizeof(val) / sizeof(val[0]);
   cout << "Maximum Profit achieved with this knapsack: " << knapSack(W, wt, val, n);
   return 0;
}

Maximum Profit achieved with this knapsack: 120

import java.util.*;
import java.lang.*;
public class Knapsack {
   public static int findMax(int n1, int n2) {
      if(n1>n2) {
         return n1;
      } else {
         return n2;
      }
   }
   public static int knapsack(int W, int wt[], int val[], int n) {
      int K[][] = new int[n+1][W+1];
      for(int i = 0; i<=n; i++) {
         for(int w = 0; w<=W; w++) {
            if(i == 0 || w == 0) {
               K[i][w] = 0;
            } else if(wt[i-1] <= w) {
               K[i][w] = findMax(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
            } else {
               K[i][w] = K[i-1][w];
            }
         }
      }
      return K[n][W];
   }
   public static void main(String[] args) {
      int[] val = {70, 20, 50};
      int[] wt = {11, 12, 13};
      int W = 30;
      int len = val.length;
      System.out.print("Maximum Profit achieved with this knapsack: " + knapsack(W, wt, val, len));
   }
}

Maximum Profit achieved with this knapsack: 120

def knapsack(W, wt, val, n):
   K = [[0] * (W+1) for i in range (n+1)]
   for i in range(n+1):
      for w in range(W+1):
         if(i == 0 or w == 0):
            K[i][w] = 0
         elif(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]
   return K[n][W]

val = [70, 20, 50];
wt = [11, 12, 13];
W = 30;
ln = len(val);
profit = knapsack(W, wt, val, ln)
print("Maximum Profit achieved with this knapsack: ")
print(profit)

Maximum Profit achieved with this knapsack: 
120