回顾DP背包问题

动态规划三个重要性质：

• 最优子结构
• 重叠子问题
• 无后效性（在构造解空间时一定要考虑）

一. 0/1背包

问题描述

01背包：有n种物品与承重为m的背包。每种物品只有一件，每个物品都有对应的重量weight[i]与价值value[i]，最大化背包价值。

对于背包问题，常见的做法是构建二维数组来构造最优解。以背包问题来说，我们的目标是通过每个物品价值value[i]和重量weight[i]，来最大化背包价值，而背包容量实际上则是优化条件。

形式化定义：设dp[i][j]为背包价值函数，dp[i][j]表示在“背包的重量为j时，取前i件物品，所能达到的最大价值”。

对于物品i，此时我们的背包有两种状态，选或不选：

1. 如果选择物品i装入背包，则需要背包留出weight[i]的重量来容纳物品i，那么若想让dp[i][j]最大，则只需让dp[i-1][j-weight[i]]最大(即前i-1件物品，使得背包容量为j-weight[i]时价值最大)；
2. 如果不选择物品i装入背包，则显然dp[i-1][j]最大，便能使得dp[i][j]最大化；

于是得到了0/1背包问题的状态转移方程：
dp[i][j]=max{d[i-1][j], dp[i-1][j-weight[i]]+value[i]}

int zeroOneBackpack(int value[], int weight[], int items, int volume) {
    /**
     * 0-1背包，二维数组实现
     * */
    int dp[items + 1][volume + 1];
    for (int i = 1; i <= items; ++i) {
        for (int j = 1; j <= volume; ++j) {
            if (weight[i] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    return dp[items][volume];
}

采用二维数组实现的方式比较直观，但是内存消耗比较大，如果数据量稍微大一点，估计就爆内存了。于是产生了一种叫“滚动数组”的方式。

滚动数组的思想是因为二维数组中存储了很多的中间状态，最后有用的状态只有dp[items][:]这一行(也就是dp表的最后一行)，滚动数组通过迭代的替换中间状态来构造最优解。通过输出每次dp[j]可以看出，一维数组就是对二维数组中的每次中间结果进行更新，最后保留最后一行。（如果内层循环j是从1开始，那么就影响了“无后效性”，相当于每个物品的数目就不是1了，这样问题就变成了完全背包问题，后续计算的结果会受到影响）

一维数组状态转移方程：
dp[j]=max{d[j], dp[j-weight[i]]+value[i]}

int zeroOneBackpack_one_diem(int value[], int weight[], int items, int volume) {
    /**
     * 0-1背包，滚动数组实现
     * */
    int dp[volume + 1];
    for (int i = 1; i <= items; i++) {
        for (int j = volume; j >= weight[i]; j--) {
            // 内存循环如果反了就变成完全背包了
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[volume];
}

打印每轮dp[]结果如下：

当i = 1 : 2  2   2   2   2   2   2   2   2   2   2   2   
当i = 2 : 2  2   5   7   7   7   7   7   7   7   7   7   
当i = 3 : 2  3   5   7   8   10  10  10  10  10  10  10  
当i = 4 : 2  3   5   7   8   10  12  13  15  17  18  20  
当i = 5 : 2  4   6   7   9   11  12  14  16  17  19  21  

二. 完全背包

问题描述

完全背包：有n种物品与承重为m的背包。每种物品有无限多件，每个物品都有对应的重量weight[i]与价值value[i]，最大化背包价值。

根据问题描述，背包能装多少就装多少，既一件物品可以放入背包中k个。
那么，可以得到完全背包的转移方程：
dp[i][j] = max{dp[I][j], dp[i-1][j - k * weight[i]] + k * value[i]}, 0 <= k*weight[i] <= j

int completelyPackage(int value[], int weight[], int items, int volume) {
    /**
     * 完全背包，二维数组实现
     * 能装多少就装多少
     * */
    int dp[items + 1][volume + 1];
    for (int i = 1; i <= items; ++i) {
        for (int j = 1; j <= volume; j++) {
            for (int k = 1; k * weight[i] <= j; k++) {
                if (dp[i - 1][j - k * weight[i]] + k * value[i] > dp[i][j])
                    dp[i][j] = dp[i - 1][j - k * weight[i]] + k * value[i];
            }
        }
    }
    return dp[items][volume];
}

同样为了避免二维数组内存开销大的问题，采用一维数组求解方式类似0/1背包
一维数组状态转移方程：
dp[j]=max{dp[j], dp[j-weight[i]]+value[i]}

int completelyPackage_one_diem(int value[], int weight[], int items, int volume) {
    /***
     * 完全背包，滚动数组实现
     */
    int dp[volume + 1];
    for (int i = 1; i <= items; ++i) {
        for (int j = weight[i]; j <= volume; ++j) {
            if (dp[j - weight[i]] + value[i] > dp[j])
                dp[j] = dp[j - weight[i]] + value[i];
        }
    }
    return dp[volume];
}

三. 多重背包

问题描述

多重背包：有n种物品与承重为m的背包。每种物品有有限件num[i]，每个物品都有对应的重量weight[i]与价值value[i]，最大化背包价值。

多重背包多了一个限制条件，那就是每个物品数量为num[i]件；
那么这个问题完全可以当成是0/1背包问题，也就是将相同的num[i]件物品i看成价值跟重量相同的num[i]件不同的物品。

于是利用0/1背包的思路，得到状态转移方程：
dp[j]=max{dp[j], dp[j-weight[i]]+value[I]}

int multiplePack(int value[], int weight[], int num[], int items, int volume) {
    int dp[volume + 1];
    for (int i = 1; i <= items; i++) {
        for (int k = 0; k < num[i]; k++) {
            for (int j = volume; j >= weight[i]; j--) {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }
    return dp[volume];
}