背包問題 - gaochundong－IT工程師數位筆記本

文章出處

背包問題描述：

有一個小偷在偷竊一家商店時發現有 n 件物品，第 i 件物品價值 v_i 元，重 w_i 磅，此處 v_i 和 w_i 都是整數。小偷希望帶走的物品價值越高越好，但他的背包至多只能裝下 W 磅的東西，W 為整數。那么，小偷應該帶走哪些物品呢？

背包問題可以包含不同的限定條件：

部分背包問題：可以帶走物品的一部分，而不必做出 0-1 的二分選擇。
0-1 背包問題：每件物品或者帶走或者留下，不能只帶走一部分或者帶走兩次以上。

部分背包問題擁有典型的貪心選擇性質，可以使用貪心算法來解決。0-1 背包問題中需要考慮背包是否填滿以取得最高的價值，在比較物品加進去或不加進去的子問題時產生了許多重疊的子問題，可以使用動態規劃算法來解決。

部分背包問題

有一個小偷在偷竊一家商店時發現有 n 件物品，第 i 件物品價值 v_i 元，重 w_i 磅，此處 v_i 和 w_i 都是整數。小偷希望帶走的物品價值越高越好，但他的背包至多只能裝下 W 磅的東西，W 為整數。為盡可能多的帶走更多的東西，小偷可以帶走物品的一部分，而不必做出 0-1 的二分選擇。那么，小偷應該帶走哪些物品呢？

最優子結構

如果從最優物品組合中去掉某物品 j 的重量 w 磅，則余下的物品必須是可以從 n - 1 件物品和物品 j 余下的 w_j - w 磅中可帶走的、重量至多為 W - w 的最值錢的一組東西。

貪心選擇性質

每件物品計算每磅的價值 v_i / w_i，小偷開始從具有最大價值的物品盡量多取一些，如果拿完該物品后背包還有余量，則可繼續取價值次大的物品，以此類推，直到背包取滿為止。

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4  
 5 namespace AlgorithmTests
 6 {
 7   class Program
 8   {
 9     static void Main(string[] args)
10     {
11       int n = 3;
12       int[] values = new int[3] { 60, 100, 120 };
13       int[] weights = new int[3] { 10, 20, 30 };
14       int W = 50;
15  
16       GreedyKnapsack(n, values, weights, W);
17  
18       Console.ReadKey();
19     }
20  
21     static void GreedyKnapsack(int n, int[] values, int[] weights, int W)
22     {
23       // 計算物品每磅價值
24       Dictionary<int, double> valuePerPound = new Dictionary<int, double>();
25       for (int i = 0; i < n; i++)
26       {
27         valuePerPound.Add(i, values[i] / weights[i]);
28       }
29  
30       // 按照每磅價值從大到小排序
31       int[] orderedPerPound = valuePerPound
32         .OrderByDescending(v => v.Value)
33         .Select(v => v.Key)
34         .ToArray();
35  
36       // 計算裝包量
37       int filling = W;
38       int totalValue = 0;
39       int j = 0;
40       List<int> packed = new List<int>();
41       while (filling > 0)
42       {
43         if (filling >= weights[orderedPerPound[j]])
44         {
45           // 完全裝入
46           filling -= weights[orderedPerPound[j]];
47           totalValue += values[orderedPerPound[j]];
48           packed.Add(weights[orderedPerPound[j]]);
49         }
50         else
51         {
52           // 部分填裝
53           totalValue += filling * values[orderedPerPound[j]] / weights[orderedPerPound[j]];
54           filling = 0;
55           packed.Add(weights[orderedPerPound[j]]);
56         }
57  
58         j++;
59       }
60  
61       Console.WriteLine(totalValue);
62       foreach (var item in packed)
63       {
64         Console.WriteLine(item);
65       }
66     }
67   }
68 }

0-1 背包問題

有一個小偷在偷竊一家商店時發現有 n 件物品，第 i 件物品價值 v_i 元，重 w_i 磅，此處 v_i 和 w_i 都是整數。小偷希望帶走的物品價值越高越好，但他的背包至多只能裝下 W 磅的東西，W 為整數。每件物品或者帶走或者留下，不能只帶走一部分或者帶走兩次以上。那么，小偷應該帶走哪些物品呢？

最優子結構

重量至多為 W 磅的價值最高的一組物品，如果從中去掉物品 j，余下的必須是小偷從除 j 以外的 n - 1 件物品中可以帶走的重量至多為 W - w_j 的價值最高的一組物品。

重復子問題

當考慮是否要把一件物品加到背包中時，必須把該物品加進去的子問題的解與不加進去的子問題的解進行比較，也就產生了許多重疊的子問題。

狀態

dp[i, j] 表示前 i 個物品裝到剩余容量為 j 的背包里能達到的最大價值。

int[,] dp = new int[n + 1, W + 1];

狀態轉移方程

考查第 i 個物品裝入背包的時候，其實是在考查第 i-1 個物品裝不裝入背包。

dp[i, j] = max{ dp[i-1, j], dp[i-1, j-weights[i-1]] + values[i-1] }

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 
 5 namespace AlgorithmTests
 6 {
 7   class Program
 8   {
 9     static void Main(string[] args)
10     {
11       int n = 3;
12       int[] values = new int[3] { 60, 100, 120 };
13       int[] weights = new int[3] { 10, 20, 30 };
14       int W = 50;
15 
16       DynamicProgrammingKnapsack(n, values, weights, W);
17 
18       Console.ReadKey();
19     }
20 
21     static void DynamicProgrammingKnapsack(int n, int[] values, int[] weights, int W)
22     {
23       // 狀態 dp[i, j] 表示前 i 個物品裝到剩余容量為 j 的背包里能達到的最大價值
24       int[,] dp = new int[n + 1, W + 1];
25 
26       // 狀態轉移方程
27       // dp[i, j] = max{ dp[i-1, j], dp[i-1, j-weights[i-1]] + values[i-1] }
28       // 考查第 i 個物品裝入背包的時候，其實是在考查第 i-1 個物品裝不裝入背包
29       for (int i = 0; i <= n; i++)
30       {
31         for (int j = 0; j <= W; j++)
32         {
33           if (i > 0 && j >= weights[i - 1])
34           {
35             int v = dp[i - 1, j - weights[i - 1]] + values[i - 1];
36             if (v > dp[i - 1, j])
37             {
38               dp[i, j] = v;
39             }
40             else
41             {
42               dp[i, j] = dp[i - 1, j];
43             }
44           }
45         }
46       }
47 
48       Console.WriteLine(dp[n, W]);
49     }
50   }
51 }