动态规划 DP 应用之 01 背包

|

问题描述：n 个不同的物品，每个物品只有一个，有价值 value 和重量 weight 两个属性；背包容量 w。求背包所能容纳的最大价值。

最优子结构：当我们把一件物品放进背包里时，会让总价值变高，并且让背包变重。对某一件物品来说，我们可以选择放或不放，然后移去这件物品所带来的影响。

c(n, w) = max( c(n-1, w), c(n-1, w-W[n]) + C[n] )
^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^
不放 -> 0 放 -> 1

n：第1个到第n个物品要放进背包内。
w：背包负重上限。
c(n, w)：第1个到第n个物品尽量塞进负重限制为w的背包时，最大价值。
W[n]：第n个物品的重量。
C[n]：第n个物品的价值。

基本算法

Bottom UP 递推

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
// 物品总数上限
const int MaxN = 100;
 
// 背包负重上限
const int MaxW = 100000;
 
// 物品
struct Item {int cost, weight;} items[MaxN];
 
// DP矩阵
int c[MaxN + 1][MaxW + 1];
 
void knapsack(int n, int w)             // n 为物品数，w 为背包负重上限
{
    memset(c, 0, sizeof(c));
 
    for (int i = 0; i < n; ++i)         // 每个物品都试试看
        for (int j = 0; j <= w; ++j)    // 每个重量都试试看
            if (j - items[i].weight < 0)
                c[i+1][j] = c[i][j];    // 放不下
            else
                c[i+1][j] = max( c[i][j], c[i][j - items[i].weight] + items[i].value );
 
    cout << "Max Value: " << c[n][w] << endl;
}

Top Down 递归

1
2
3
4
5
6
7
8
9
10
11
12
int knapsack(int W)
{
    int i, space, max, maxi, t;
    if (maxKnow[W] != -1) return maxKnown[W];
    
    for (i = 0, max = 0; i < N; i++)
        if ((sapce = W - items[i].weight) >= 0)
            if ((t = knapsack(space) + items[i].value) > max)
                { max = t; maxi = i; }
    maxKnown[W] = max; itemKnown[W] = items[maxi];
    return max
}

空间优化

因为计算时只需要用到上方和左上方的格子，所以只需要一个单行数组就可以了。不过计算次序需要改为由后向前，才不会覆盖掉需要用来计算的格子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MaxN = 100, MaxW = 100000;
struct Item {int cost, weight;} items[MaxN];
int c[MaxW + 1];
 
void knapsack(int n, int w)
{
    memset(c, 0, sizeof(c));
 
    for (int i = 0; i < n; ++i)
    {
        int weight = items[i].weight, cost = items[i].cost;
        for (int j = w; j - weight >= 0; --j)
            c[j] = max( c[j], c[j - weight] + cost );
    }
 
    cout << "Max Value: " << c[w] << endl;
}

Python

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
from numpy import *

def knapsack_iter(W, items):
    A = zeros(2 * W).reshape(2, W)
    i = 0

    for (v, w) in items:
        A[(i+1)%2][:w] = A[i%2][:w]
        A[(i+1)%2][w:] = maximum(A[i%2][w:], A[i%2][:W-w] + v)
        i += 1
    return A[i%2][W-1]


def knapsack_recur(W, items):
    # top-down solution with memoization via hashtable
    N = len(items)
    A = {}
    def A_(i, j):
        if (str(i)+','+str(j)) in A: return A[str(i)+','+str(j)] # memoization
        if i == 0: return 0
        v, w = items[i]
        if j-w < 0:
            result = A_(i-1, j)
            A[str(i)+','+str(j)] = result # memoization
            return result
        else:
            result = max(A_(i-1, j), A_(i-1, j-w) + v)
            A[str(i)+','+str(j)] = result # memoization
            return result
    return A_(N-1, W-1)