设计与分析 - 0-1 背包

我们在本教程前面讨论了使用贪婪方法的分数背包问题。结果表明，贪心法给出了分数背包的最优解。然而，本章将介绍使用动态规划方法的 0-1 背包问题及其分析。

与小数背包不同，物品总是完全存储，而不使用它们的小数部分。要么该物品被添加到背包中，要么不被添加到背包中。这就是为什么，这种方法被称为0-1 背包问题。

因此，在 0-1 背包的情况下， x _i的值可以是0或1，其他约束保持不变。

0-1背包不能用贪心法解决。贪婪方法并不能确保该方法的最佳解决方案。在许多情况下，贪婪方法可能会给出最佳解决方案。

0-1背包算法

问题陈述- 小偷正在抢劫一家商店，他的背包中最多可以携带W的重量。有n 个^{物品，第 i个}物品的重量为 wi ，选择该物品的利润为pi。小偷应该拿走什么物品？

令 i 为W美元的最优解S中编号最高的项。那么S' = S − {i}是W – w _i美元的最优解，解 S 的值是 Vi_加上子问题的值。

我们可以用下面的公式来表达这个事实：定义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, wW]进行跟踪。

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,ww\left [ i \right ] \right ]+P\left [ i \right ] \right\} $$

通过使用公式计算所有值，获得的表格将是 -

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

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

分析

该算法需要 Ɵ(nw) 次，因为表 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