10.動態規劃（3）——0-1背包問題

在上一篇《9.動態規劃（2）——子集和問題》中，談到了什麼是子集和問題，以及實現。背包問題實際也是子集和問題的一種，不過背包問題不是「判斷問題」而是一個「最優問題」。而背包問題實際上又分為「0-1背包」，「完全背包」，本文對「0-1背包」進行講解。

問題：有n個物品，每個物品的重量為weigh[i]，每個物品所對應的價值為price[i]，現在有一個背包，背包所能承受的重量為W，問背包能裝下的物品總價值最大是多少？

定義s[i, j]表示前i個物品的總價值，j為背包的承重量。當j = W或者最接近於W且小於W時，此時就是問題的解。

對於「動態規劃」的關鍵就是要找到其遞推公式，遞推公式往往會將一個問題以某個值為邊界拆分為兩部分。背包問題的求解是子集和問題的最優化求解，在《9.動態規劃（2）——子集和問題》中分析過遞推公式的推導工程，在這裡重新分析推導。

分析：s[i, j]表示前i個物品，如果前i - 1個物品價值已經達到背包承重量j的極限，那麼第i個物品就不能放進去(j - wi < 0)，此時就可表示s[i, j] = s[i - 1, j]。但如果第i - 1個物品未達到背包承重量j的極限(j - wi >= 0)，此時我們計算前i - 1個物品的價值就是s[i - 1, j - wi]，此時加上第i個物品的價值就可以表示為s[i - 1, j - wi] + pi。

綜上得到遞推公式：

舉例：物品的重量集合w = (2, 4, 1, 5, 3)，物品的價格集合 p = (4, 5, 19, 3, 2)，背包重量6。通過上面的遞推公式，將這個背包問題利用矩陣來表示，第6列的最大值即為背包重量為6時的最大價值。

Java

1 package com.algorithm.dynamicprogramming;
2
3 import java.util.Arrays;
4
5 /**
6 * 0-1背包問題
7 * | s[i - 1, j] (j - wi < 0) 8 * s[i, j] = | | s[i - 1, j] 9 * | Max | (j - wi >= 0)
10 * | | s[i - 1, j -wi] + pi
11 * Created by yulinfeng on 7/3/17.
12 */
13 public class KnapsackProblem {
14 public static void main(String[] args) {
15 int weight = {2, 4, 1, 5, 2};
16 int price = {4, 5, 19, 3, 2};
17 int knapsackWeight = 6;
18 int value = knapsackProblem(weight, price, knapsackWeight);
19 System.out.println(value);
20 }
21
22 /**
23 * 動態規劃求解0-1背包問題
24 * @param weight 物品重量
25 * @param price 物品價值
26 * @param knapsackWeight 背包承重量
27 * @return
28 */
29 private static int knapsackProblem(int[] weight, int[] price, int knapsackWeight) {
30 int row = weight.length + 1;
31 int col = knapsackWeight + 1;
32 int solutionMatrix = new int[row][col];
33 int values = new int[row];
34 values[0] = 0;
35 for (int i = 0; i < row; i++) { 36 solutionMatrix[i][0] = 0; 37 } 38 for (int j = 0; j < col; j++) { 39 solutionMatrix[0][j] = 0; 40 } 41 42 for (int i = 1; i < row; i++) { 43 for (int j = 1; j < col; j++) { 44 solutionMatrix[i][j] = solutionMatrix[i - 1][j]; 45 if (j - weight[i - 1] >= 0 && solutionMatrix[i - 1][j - weight[i - 1]] + price[i - 1] > solutionMatrix[i][j]) {
46 solutionMatrix[i][j] = solutionMatrix[i - 1][j - weight[i - 1]] + price[i - 1];
47 }
48 }
49 values[i] = solutionMatrix[i][col - 1];
50 }
51 Arrays.sort(values);
52 return values[values.length - 1];
53 }
54 }

Python3

1 def knapsack_problem(weight, price, knapsackWeight):
2 """
3 0-1背包問題
4 | s[i - 1, j] (j - wi < 0) 5 s[i, j] = | | s[i - 1, j] 6 | Max | (j - wi >= 0)
7 | | s[i - 1, j -wi] + pi
8
9 Created by yulinfeng on 7/3/17.
10 """
11 row = len(weight) + 1
12 col = len(price) + 1
13 solutionMatrix = [[0 for c in range(col)] for r in range(row)]
14 values = [0] * row
15 for i in range(row):
16 solutionMatrix[0][i] = 0
17 for j in range(col):
18 solutionMatrix[j][0] = 0
19 for m in range(1, row):
20 for n in range(1, col):
21 solutionMatrix[m][n] = solutionMatrix[m - 1][n]
22 if n - weight[m - 1] >= 0 and solutionMatrix[m - 1][n - weight[m - 1]] + price[m - 1] > solutionMatrix[m][n]:
23 solutionMatrix[m][n] = solutionMatrix[m - 1][n - weight[m - 1]] + price[m - 1]
24 values[m] = solutionMatrix[m][col - 1]
25
26 values.sort
27 return values[len(values) - 1]
28
29 weight = (2, 4, 1, 5, 2)
30 price = (4, 5, 19, 3, 2)
31 knapsackWeight = 6
32 value = knapsack_problem(weight, price, knapsackWeight)
33 print(value)

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！