0%

0/1 Knapsack

Posted on Edited on

0/1 背包問題

0/1 knapsack problem

  • n個物品
  • 重量w1, w2, w3, …, w(n)
  • 值(利潤) v1, v2, …, v(n)
  • 背包載重容量 (capacity) W

表格

V=>Value
陣列V[0..n, 0..W]。
元素V[i, w], 1<=i<=n(表示物品1,2,…,n), 且 0<=w<=W。
V[n,W]就是解答

遞迴關係

初始化設定

V[0, w]=0 for 0<=w<=W
表示 沒有任何物品放入背包中

關係

image alt
第二列: 第i個物品可能放入袋子中, 比較不放跟放誰價值高
第三列: 第i個物品的重量已經大於w了 不放

由底而上填表

image alt

演算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Algorithm 0/1 KnapSack
Input: 最大容量W, n個物品, 重量w(i), 價值v(i), 1<=i<=n, V表格
// 初始化
for(w=0 to W)
    V[0][w]=0
for(i=1 to n)
    for(w=0 to W)
        if w[i]<=w
            V[i][w]=max{V[i-1][w],v[i]+V[i-1][w-w[i]]}
        else
            V[i][w]=V[i-1][w]
            
return V[n][W]

時間複雜度: O(n*W) n個物品乘以最大重量

例子

image alt

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
using namespace std;
void knapsack(int W, int* weight, int* value) {
    // table
    int **V;
    V = new int*[5 + 1];
    for (int i = 0; i <= 5 + 1; ++i) {
        V[i] = new int[W + 1];
    }
    // 初始化
    for (int w = 0; w <= W; w++)
    {
        V[0][w] = 0;
    }
    // write table
    for (int i = 1; i <= 5; i++)
    {
        for (int w = 0; w <= W; w++)
        {
            if (weight[i] <= w)
            {
                V[i][w] = max(V[i - 1][w], value[i] + V[i - 1][w - weight[i]]);
            }
            else
            {
                V[i][w] = V[i - 1][w];
            }
        }
    }
    cout << "背包總價值為: " << V[5][W] << endl;
}
int main()
{
    int num_i = 1;
    //cin >> num_i;
    for (int i = 0; i < num_i; i++)
    {
        // 固定5個物品
        int W = 10;
        int weight[6] = { -1, 3, 1, 4, 2, 5 }; // [0] 不用
        int value[6] = { -1, 7, 10, 9, 4, 8 }; // [0] 不用
        //cin >> W;
        //for (int i = 1; i <= 5; i++)
        //{
        //  cin >> weight[i];
        //}
        //for (int i = 1; i <= 5; i++)
        //{
        //  cin >> value[i];
        //}
        knapsack(W, weight, value);
    }
    system("pause");
    return 0;
}
/*
Sample input
3
10
3 1 4 2 5
7 10 9 4 8
17
7 4 8 7 12
3 2 1 4 7
38
12 7 32 5 21
8 5 19 8 14
Sample output
30
9
30
*/