动态规划：0-1背包问题

1. 背包问题

给定一组物品，每种物品都有自己的重量(Weight)和价格(Value)，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。

Input:

1. 一个容量为W(Weight)的背包
2. 有N件物品，第i件物品的重量是w[i]，价值是v[i]（V：Value）。

Output: 求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

Knapsack is basically means bag. A bag of given capacity.

We want to pack n items in your luggage.

1. The ith item is worth $v_i$ dollars and weight $w_i$ pounds.
2. Take as valuable a load as possible, but cannot exceed W pounds.
3. $v_i, w_i, W$ are integers.

背包问题可进一步分为两种类型：

1. 部分背包（Fractional Knapsack）: 物品可以切分，部分背包问题可以用贪心算法解决。
2. 0/1背包（0/1 Knapsack Problem）: 物品不可以被切分，要么整个拿走，要不不拿。这就是为什么它被称为0/1背包问题。贪婪方法无法解决此问题，因为用贪心算法的思路，背包最后可能没法装满。这类问题一般用动态规划算法解决。

2. 0/1背包问题示例

2.1 初始状态

例如，这个背包能装的最大重量是W（=11）公斤。有N（=5）件物品可供选择。每件物品的重量(w, weight)和价值(v, value)如下表所示。

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0
w2=2; v2=6	0
w3=5; v3=18	0
w4=6; v4=22	0
w5=7; v5=28	0

对于所有行的V[i,0]置为0，即背包容量为0时能装的价值为0。所有的V[0,i]置为0，即没有物品可装时总价值为0。

2.2 有物品1可供装入

数组的[i，j]项代表V[i，j]，如果最大容量为j，则使用项目的前“i”行可获得的最佳价值。为方便讨论，i从1开始，j从0开始。

我们从第一行开始，即假定只有1个物品G1(w1,v1)，在背包总容量在0~11之间变动时，能装的总的最大价值Value。

1. 当背包容量是0时，物品G1不能装入，故总价值V[1,0] = 0。
2. 当背包容量是1时，物品G1能装入，故总价值V[1,1] = 1。
3. 当背包容量继续增加到2~11，还是只有物品G1可供装入，故总价值不变V[1,2] = 1，… V[1,11]=1。

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0	1	1	1	1	1	1	1	1	1	1	1
w2=2; v2=6	0
w3=5; v3=18	0
w4=6; v4=22	0
w5=7; v5=28	0

2.3 有物品1~2可供装入

每次的选择策略公式如下： V[i, j] = max {V[i - 1, j], vi + V[i - 1, j - wi]

例如，对于V[2,2]：

1. V[i - 1, j] = V[1,2] = 1，即不选择装入当前物品的话，最大的价值即上一行对应的值。
2. vi + V[i - 1, j - wi] = 6 + V[1, 2-2] = 6，即选择装入当前物品的价值（6） + 从上一行找到剩下的重量（0）能装下的最大价值。
3. 比较后，取后者。

例如，对于V[2,3]：

1. V[i - 1, j] = V[1,3] = 1，即不选择装入当前物品的话，最大的价值即上一行对应的值（1）。
2. vi + V[i - 1, j - wi] = 6 + V[1, 3-2] = 7，即选择装入当前物品的价值（6） + 从上一行找到剩下的重量（1）能装下的最大价值（1）。
3. 比较后，取后者。

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0	1	1	1	1	1	1	1	1	1	1	1
w2=2; v2=6	0	1	6	7	7	7	7	7	7	7	7	7
w3=5; v3=18	0
w4=6; v4=22	0
w5=7; v5=28	0

2.4 有物品1~3可供装入

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0	1	1	1	1	1	1	1	1	1	1	1
w2=2; v2=6	0	1	6	7	7	7	7	7	7	7	7	7
w3=5; v3=18	0	1	6	7	7	18	19	24	25	25	25	25
w4=6; v4=22	0
w5=7; v5=28	0

以V[3,7]为例：

1. V[i - 1, j] = V[2, 7] = 7，即不选择装入当前物品的话，最大的价值即上一行对应的值（7）。
2. vi + V[i - 1, j - wi] = 18 + V[2, 7-5] = 18 + 6 = 24，即选择装入当前物品的价值（18） + 从上一行找到剩下的重量（2）能装下的最大价值（6）。
3. 比较后，取后者。

V[3, 7] = max {V[3 - 1, 7], v3 + V[3 - 1, 7 - w3]
         = max {V[2, 7], 18 + V[2, 7 - 5]} 
         = max {7, 18 + 6}
         = 24

2.5 有物品1~4可供装入

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0	1	1	1	1	1	1	1	1	1	1	1
w2=2; v2=6	0	1	6	7	7	7	7	7	7	7	7	7
w3=5; v3=18	0	1	6	7	7	18	19	24	25	25	25	25
w4=6; v4=22	0	1	6	7	7	18	22	24	28	29	29	40
w5=7; v5=28	0

注意观察，V[4,6]选择的是装入物品4，但是V[4,7]则选择了不装入物品4，上一行V[3,7]的价值更大。

2.6 有物品1~5可供装入

重量限制(i)	0	1	2	3	4	5	6	7	8	9	10	11
没有物品	0	0	0	0	0	0	0	0	0	0	0	0
w1=1; v1=1	0	1	1	1	1	1	1	1	1	1	1	1
w2=2; v2=6	0	1	6	7	7	7	7	7	7	7	7	7
w3=5; v3=18	0	1	6	7	7	18	19	24	25	25	25	25
w4=6; v4=22	0	1	6	7	7	18	22	24	28	29	29	40
w5=7; v5=28	0	1	6	7	7	18	22	28	29	34	35	40

以上测试数据，供调试使用：5 11 1 1 2 6 5 18 6 22 7 28

3 算法总结和代码示例

#include <iostream>  
#include <algorithm> // std::max
#define MAX_W 1001 //最大的容量（重量, Weight）
#define MAX_N 101  //最多物品数量（Number）
using namespace std;

struct Goods
{
    int weight;
    int value;
};
Goods goods[MAX_N];        //物品表

//价值表，第一维（行）表示物品，第二维表示背包的容量（列）
//        对应的值为有前i个物品可选，容量最多为j的情况下的最大价值。初始化为0
int V[MAX_N][MAX_W] = {0}; 

int main()
{
    int n; //物品数量
    int w; //背包总容量
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
        cin >> goods[i].weight >> goods[i].value;
    
    //第0行表示没有物品时最大价值为0；第0列表示容量为0时价值为0，已初始化为0
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= w; j++)
        {
            if (j < goods[i].weight) //当前物品重量超过了价值表当前列
            {
                V[i][j] = V[i - 1][j];
            }
            else
            {
                // 【背包容量为j的情况下，在选择是否装入第i个商品时，总价值分析】
                // 假如不装入当前物品：V[i - 1][j]，直接用上一次的结果（即上一行）
                // 假如装入当前物品：
                //    装入当前物品的价值 + goods[i].value
                //    去掉当前物重的容量下可装最大价值(V[i - 1][j - goods[i].weight])，来自上一行
                //    这是动态规划的核心部分，利用上一次的结果。
                // 最后两者取最大值
                V[i][j] = max(V[i - 1][j], goods[i].value + V[i - 1][j - goods[i].weight]);
            }
        }

    cout << V[n][w] << endl;

    return 0;
}

4. 编程

1. noip-j-05-3 采药
2. noip-j-06-2 开心的金明