0-1 背包问题

我们之前讨论了使用贪婪方法的分数背包问题本教程将介绍贪婪算法。贪婪算法给出了分数背包问题的最优解。然而，本章将介绍使用动态规划方法求解 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]

The following examples will establish our statement.

Example

Let us consider that the capacity of the knapsack is W = 8 and the items are as shown in the following table.

解决方案

使用 0-1 背包的贪婪方法，背包中存储的重量为 A+B = 4，最大利润为 2 + 4 = 6。但是，该解决方案并非最优解。

因此，必须采用动态规划来解决 0-1 背包问题。

步骤 1

构建一个邻接表，行记录背包的最大重量，列记录物品的重量和利润。

表中存储的值是重量不超过背包最大重量（每行指定值）的物品的累计利润。

因此，我们在第 0 行和第 0 列添加零，因为如果物品的重量为 0，那么它就没有重量了；如果背包的最大重量为 0，则背包中不能添加任何物品。

其余值填充了背包中每列可存储物品和重量所能实现的最大利润。

存储利润值的公式为 −

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

通过使用该公式计算所有值，得到的表格为 −

要找到要添加到背包中的物品，请从表中识别最大利润，并确定构成利润的物品，在本例中为 {1, 7}。

最优解为 {1, 7}，最大利润为 12。

分析

由于表 c 有 (n+1).(w+1) 个条目，因此该算法需要 Ɵ(n.w) 次，其中每个条目需要 Ɵ(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