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