动态规划——01背包问题

01背包：

一.二维数组实现01背包

包括物品和背包，但每个物品的数量只有一个，所以只需要考虑选一个和不选两种情况。

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

在下面的讲解中，我举一个例子：

背包最大重量为4。

物品为：

问背包能背的物品最大价值是多少？

1.确定dp数组以及下标的含义

二维dp数组，通过上面的表格和所求可以得出，需要两个维度分别表示物品和背包容量。

dp[i][j]其中i表示物品，j表示背包容量，dp[i][j]表示从下标为[0-i]的物品里面任意取，放进容量为j的背包，价值总和最大是多少。所以根据上述含义，则dp[1][4]表示任取 物品0，物品1 放进容量为4的背包里，最大价值是 dp[1][4]。

2.确定递推公式

对于递推公式，主要明确有哪些方向可以推导出dp[i][j]。

求取 dp[1][4] 有两种情况：

1. 放物品1
2. 还是不放物品1

用dp[1][4]的状态来举例：

dp[1][4]表示任取 物品0，物品1 放进容量为4的背包里，最大价值是 dp[1][4]。那就要找到最大价值，有两种情况可能找到最大价值，一种是只放物品0不放物品1，还有就是放物品0和物品1两种。只有当背包容量大于物品1的重量的时候才会出现第二种情况。

如果不放物品1， 那么背包的价值应该是 dp[0][4] 即 容量为4的背包，只放物品0的情况。

如果放物品1， 那么背包要先留出物品1的容量，目前容量是4，物品1 的容量（就是物品1的重量）为3，此时背包剩下容量为1。

容量为1，只考虑放物品0 的最大价值是 dp[0][1]，这个值我们之前就计算过。所以 放物品1 的情况 = dp[0][1] + 物品1 的价值。

两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）

dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)。

但这个地方我一开始有个疑惑，为什么放物品1的时候是dp[0][1]？

1.为什么是dp[……][1]而不是dp[……][4]?

当我们在dp[1][4]的状态下决定放物品1时，物品1已经占用了容量空间了，而且后面已经把物品1的价值算上了，所以说明物品1已经放上了。如果容量空间不变的话，就说明加上物品1的价值之后，还有这么多空间可以用，那就会在遍历后面的物品的时候，本来不够容量空间不可以放的物品仍然可以放上，这肯定不对，这多加上了一部分价值。所以应该是去掉加入这个物品重量之后的。

2.为什么是dp[0][1]而不是dp[1][1]呢？

如果是dp[1][1]表示考虑物品0和物品1放入容量为1的背包中的最大价值，但是我们已经把物品1的价值加上了，所以说明如果是dp[1][1]的话物品1被重复放入(虽然实际放不下，但概念上错误)。

3.那在考虑是否放物品1的时候，放物品0了吗？

我们要理解dp[1][4]的本质是已经考虑完物品1和物品0，背包容量为4的最优解。在dp[0][……]的这一行，我们已经只考虑物品0，各种容量下的最优解，这个最优解可能放了物品0也可能没放，但一定是最优解。

dp[0][剩余容量] 不是"还没放物品0"，而是：

• 在只允许使用物品0的情况下
• 用给定容量能获得的最大价值
• 这个最优解里，物品0可能放了，也可能没放

假设举例dp[1][4]=max{10,15},最后dp[1][4]=15，这个结果就是最优解。方案一不放物品1，价值是10；方案二放物品1，价值是15，这个结果肯定是没放物品0的时候是最优解，所以只要是最优解即可，某个物品都有可能放了或者没放。

4.但是可能有的人疑惑那多个物品放到背包中是怎么实现的？

注意到dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)，根据上述递推公式可以发现当放物品1的时候，还要加上之前遍历的物品，这里由于我们之前算的dp[0][1]结果为0，所以这里相当于只有物品1被加入。但是从这里我们可以看出，只要容量够了，就可以把物品0加入到背包中，所以是可以实现多个物品加入背包的。而且从这里也可以看出来，每一个dp[][]都是最优解，所以只要符合题意，加上的价值也是最优解，所以最后的结果肯定是最大价值。

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组初始化

一定要根据dp[i][j]的定义和递推公式得到。

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

放物品1 的情况 = dp[0][1] + 物品1 的价值，推导方向如图：

根据递推公式发现，dp[i][j]是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

4.确定遍历顺序

有两个遍历维度：物品和背包重量

所以就出现两个遍历顺序，先遍历物品还是先遍历背包重量呢？

两种遍历顺序都正确！！！

因为二维dp数组的状态转移只依赖于上方或者是左上方，所以无论按什么顺序计算，只要：

1. 计算dp[i][j]时，dp[i-1][...]已经算好了
2. 不会用到同一行dp[i][...]的其他值

先遍历物品，再遍历背包(外层i，内层j)

固定物品i，计算它在所有容量j下的dp值 i=1: 计算dp[1][0], dp[1][1], ..., dp[1][bagweight] i=2: 计算dp[2][0], dp[2][1], ..., dp[2][bagweight] ...

假设有3个物品，容量4: (1,0) (1,1) (1,2) (1,3) (1,4) ← 先算完物品1的所有容量 (2,0) (2,1) (2,2) (2,3) (2,4) ← 再算物品2 (3,0) (3,1) (3,2) (3,3) (3,4) ← 最后物品3

先遍历背包在遍历物品(外层j，内层i)

固定容量j，计算所有物品在这个容量下的dp值 j=0: 计算dp[1][0], dp[2][0], dp[3][0], ... j=1: 计算dp[1][1], dp[2][1], dp[3][1], ... ...

(1,0) (2,0) (3,0) ← 先算完容量0的所有物品 (1,1) (2,1) (3,1) ← 再算容量1 (1,2) (2,2) (3,2) ← 容量2 (1,3) (2,3) (3,3) ← 容量3 (1,4) (2,4) (3,4) ← 最后容量4

根据上述计算过程，都满足上述条件，计算dp[i][j]的时候，dp[i-1][……]已经算好，不会影响后面的推导，所以两种遍历顺序都可以。

例题一：携带研究材料（与上述完全一样）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。 

第三行包含 M 个正整数，代表每种研究材料的价值。

输出描述

输出一个整数，代表小明能够携带的研究材料的最大价值。

输入示例

6 1 2 2 3 1 5 2 2 3 1 5 4 3

输出示例

5

提示信息

小明能够携带 6 种研究材料，但是行李空间只有 1，而占用空间为 1 的研究材料价值为 5，所以最终答案输出 5。 

数据范围：
1 <= N <= 5000
1 <= M <= 5000
研究材料占用空间和价值都小于等于 1000

代码展示

#include <stdio.h> #include <stdlib.h> // 获取最大值 int max(int a, int b) { return a > b ? a : b; } int main() { int n, bagweight; // bagweight代表行李箱空间 scanf("%d %d", &n, &bagweight); // 动态分配数组 int *weight = (int *)malloc(n * sizeof(int)); // 存储每件物品所占空间 int *value = (int *)malloc(n * sizeof(int)); // 存储每件物品价值 for(int i = 0; i < n; ++i) { scanf("%d", &weight[i]); } for(int j = 0; j < n; ++j) { scanf("%d", &value[j]); } // 动态分配二维dp数组 // dp[i][j]代表行李箱空间为j的情况下,从下标为[0, i]的物品里面任意取,能达到的最大价值 int **dp = (int **)malloc(n * sizeof(int *)); for(int i = 0; i < n; ++i) { dp[i] = (int *)malloc((bagweight + 1) * sizeof(int)); // 初始化为0 for(int j = 0; j <= bagweight; ++j) { dp[i][j] = 0; } } // 初始化第一行 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } // 动态规划计算 for(int i = 1; i < n; i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量 if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值 } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } } printf("%d\n", dp[n - 1][bagweight]); // 释放动态分配的内存 for(int i = 0; i < n; ++i) { free(dp[i]); } free(dp); free(weight); free(value); return 0; }

例题二：

（1）砝码称重（和上述有点不一样）

题目描述

你有一架天平和 N 个砝码, 这 N 个砝码重量依次是 W1​,W2​,⋯,WN​ 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N 。

第二行包含 N 个整数: W1​,W2​,W3​,⋯,WN​ 。

输出格式

输出一个整数代表答案。

输入

3 1 4 6

输出

10

说明/提示

【样例说明】

能称出的 10 种重量是: 1、2、3、4、5、6、7、9、10、11 。

【评测用例规模与约定】

对于 50% 的评测用例, 1≤N≤15 。

对于所有评测用例, 1≤N≤100,N 个砝码总重不超过 105。

代码实现：

#include <stdio.h> #include <stdlib.h> // 用于abs函数 int n, ans, sum, w[101], dp[101][100001]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &w[i]); sum += w[i]; } for (int i = 1; i <= n; i++) { for (int j = sum; j > 0; j--) { // 注意：这里j从sum递减到1 if (j == w[i]) { dp[i][j] = 1; } else if (dp[i-1][j]) { dp[i][j] = 1; } else if (dp[i-1][j + w[i]]) { dp[i][j] = 1; } else if (dp[i-1][abs(j - w[i])]) { dp[i][j] = 1; } } } for (int i = 1; i <= sum; i++) { if (dp[n][i]) { ans++; } } printf("%d", ans); return 0; }

解析一下上述代码思路：

上述题目不像前面的题目，没有那种需要计算的递推公式，要是按照上次题目的代码来写dp数组的含义，我们可以写出i表示前i个砝码可称j重量的物品，但是无法写出dp数组到底是什么含义。所以我们就重回题目发现一些蛛丝马迹，注意到最后要求的是可称的重量数，第一时间想到的是dp数组就直接表示所求的，也就自然而然想到如果可称那就dp数组不断累加，这就想到标志变量，通过标志变量来进行累加，但这样好像就无法发挥dp数组中i,j的含义，只是表示一个累加的变量，所以肯定不能让dp数组累加。那就如何发挥dp数组中的i,j呢？当然就是dp数组表示一个标志变量，用另一个变量来累加，刚好弥补dp数组还没有含义的欠缺。

dp[i][j] = 1 表示：使用前i个砝码（即第1个到第i个砝码），能够称出重量j

上述dp数组中的i,j表示的含义与上次题目中的含义基本相同，也降低了一点难度。

解析一下上述四种情况：

情况1：j == w[i]

• 只用第i个砝码就能称出重量j
• 也就是直接用输入的N个砝码先称出N个重量

情况2：dp[i-1][j]

• 不使用第i个砝码，前i-1个已经能称出j
• 第i个砝码闲置

情况3：dp[i-1][j + w[i]]

• 第i个砝码放在与被称物同一侧（左边）

数学推导

• 左边：被称物(j) + 第i个砝码(w[i])
• 右边：其他砝码的组合
• 平衡条件：j + w[i] = 其他砝码的重量
• 因此：其他砝码的重量 = j + w[i]

通俗解释：

如果前i-1个砝码能称出（j+w[i]）这个重量，那么把第i个砝码从右边移到左边，就能称出j，刚好还是符合dp数组等于1。（上述是用写出来的dp数组去推dp[][]==1这个条件的）。也可以根据使用前i个砝码称出j重量，来写当第i个砝码在左边还是右边的两种情况。

当第i个砝码在左边时，也就是左边又多了w[i]的重量，前i-1个砝码就要称j+w[i]才能保证前i个砝码称出重量为j的物品。这样刚好保证新加上的第i个砝码重量抵消右边的w[i]，保证题意。

情况4：dp[i-1][abs(j - w[i])]

• 第i个砝码放在与被称物不同侧（右边）

数学推导

• 左边：被称物(j)
• 右边：第i个砝码(w[i]) + 其他砝码的组合
• 平衡条件：j = w[i] + 其他砝码的重量
• 因此：其他砝码的重量 = j - w[i]（取绝对值是因为重量不能为负）

通俗解释：

如果前i-1个砝码能称出|j-w[i]|这个重量，那么加上第i个砝码在另一侧，就能称出j

与上述情况3几乎是一样的思路。

注意事项！！！

j从sum递减到1：

根据上述if语句里面的条件必须是已知的，才能进行后面的判断。因为i从小到大开始遍历，所以i-1肯定是已经推得的了。但是根据j+w[i]→j，j+w[i]>j所以说明j要从大到小遍历。

（2）砝码来组合(分组背包)

题目描述

小 Y 同学近来得到了一套新的砝码玩具，内含有 1g，2g，5g，10g 的砝码各若干枚（其 总重≤1000g），游戏的玩法是：由系统自动给出一个重量值，若给定的砝码能够组合成所需的重量，小 Y 要填写出一共有多少种组合方式，否则填写 cannot compose。小 Y 同学总是找不出所有的情况，你能编个程序来帮助他吗？

输入

第一行输入 a1,a2,a3,a4，分别代表 1g，2g，5g，10g10g 砝码的数量。
第二行输入 weight，代表重量值。

输出

若能够组合，输出砝码一共有多少种组合方式，否则输出 cannot compose。

输入

1 2 3 3

20

输出

4

代码实现：

#include<stdio.h> int main() { int a[4]; int weight,i,j; for(i=0;i<4;i++){ scanf("%d",&a[i]); } scanf("%d",&weight); int dp[5][1001]={0}; int values[4] = {1, 2, 5, 10}; dp[0][0]=1; int k; for(i=1;i<=4;i++){ for(j=0;j<=weight;j++){ dp[i][j]=dp[i-1][j]; for(k=1;k<=a[i-1];k++){ if(j >= k * values[i-1]){ dp[i][j]=dp[i][j]+dp[i-1][j-k*values[i-1]]; } } } } if(dp[4][weight]>0){ printf("%d",dp[4][weight]); }else{ printf("cannot compose"); } return 0; }

一开始我感觉有点像分组背包，因为组已经分好了，就是砝码的种类数。而每种砝码中按个数划分成不同的种类，dp[i][j]表示从1~i组中每组挑选一种商品总量不超过j，因为这里j是确定的，就是weight不变，所以可能有一点不一样。更要注意的是，每种砝码是有重量区别的，不能和分组背包中“摆花”问题一样，就只考虑拿取每组中花盆数量，这里还需要考虑每组的大小。除了这个小小的不同，就可以利用分组背包来解决上述题目。

“摆花”问题没有把dp[i][j]=dp[i-1][j];拿出来单独考虑，这是为什么呢？

关键点在于：k从0开始循环！

当k=0的时候：

f[i][j] += f[i-1][j-0] = f[i-1][j]这就是不考虑第i组的情况，实际隐含在代码里面。

而上述题目是从k=1开始循环的，所以要把不考虑第i组的情况单独拿出来。

解析一下下面代码：

for(i=1;i<=4;i++){
        for(j=0;j<=weight;j++){
            dp[i][j]=dp[i-1][j];
            for(k=1;k<=a[i-1];k++){//遍历的是每组的砝码数量
                if(j >= k * values[i-1]){
                    dp[i][j]=dp[i][j]+dp[i-1][j-k*values[i-1]];//到这里还是和“摆花”问题几乎一样，但不要忘了因为二者小小的区别造成的k*values[i-1]。
                }
            }
        }
    }

我认为j是确定的weight，为什么上述代码还需要遍历j，遍历所有重量呢？

虽然最终我们只关心dp[weight]（组成目标重量的方案数），但在计算过程中，我们需要知道所有中间重量的方案数，因为这些中间结果会被用来推导最终结果。

例题三：装箱问题

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式

• 共一行一个整数，表示箱子最小剩余空间。

输入

24 6 8 3 12 7 9 7

输入

0

说明/提示

对于 100% 数据，满足 0<n≤30，1≤V≤20000。

代码实现：

1.下面的代码中dp[i][j]表示前 i 个物品在容量为 j 的背包中的最大价值。（这是正常的dp数组表示）。但注意数组是从0开始的，所以有些地方要改动一下。(其实不如表示前i+1个物品好写代码)

#include<stdio.h> #include<stdlib.h> int max(int a,int b){ if(a>b){ return a; }else{ return b; } } int main() { int q; scanf("%d",&q); int n; scanf("%d",&n); int i,j; int* v=(int *)malloc(n*sizeof(int)); for(i=0;i<n;i++){ scanf("%d",&v[i]); } int** dp=(int **)malloc((n+1)*sizeof(int*)); for(i=0;i<=n;i++){ dp[i]=(int *)malloc((q+1)*sizeof(int)); for(j=0;j<=q;j++){ dp[i][j]=0; } } for(i=1;i<=n;i++){ for(j=0;j<=q;j++){ if(j<v[i-1]){ dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+v[i-1]); } } } printf("%d\n",q-dp[n][q]); for(i=0;i<=n;i++){ free(dp[i]); } free(dp); free(v); return 0; }

解析一下部分代码：

装箱代码： for(i=0;i<=n;i++){//1.区别 dp[i]=(int *)malloc((q+1)*sizeof(int)); for(j=0;j<=q;j++){ dp[i][j]=0; } }2.区别 for(i=1;i<=n;i++){ for(j=0;j<=q;j++){ if(j<v[i-1]){3.区别 dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+v[i-1]); } } } 携带研究材料代码：dp[i][j]表示的是前i+1个物品在容量为 j 的背包中的最大价值。 for(int i = 0; i < n; ++i) { dp[i] = (int *)malloc((bagweight + 1) * sizeof(int)); // 初始化为0 for(int j = 0; j <= bagweight; ++j) { dp[i][j] = 0; } } // 初始化第一行 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } // 动态规划计算 for(int i = 1; i < n; i++) { // 遍历物品 for(int j = 0; j <= bagweight; j++) { // 遍历行李箱容量 if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; // 如果装不下这个物品,那么就继承dp[i - 1][j]的值 } else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } }

观察上述两个代码，区别在于上述：1.2.3！！！

1.

假设有 n=3 个物品：

• i=0：表示前0个物品（没有物品）
• i=1：表示前1个物品（只考虑物品1）
• i=2：表示前2个物品（考虑物品1和物品2）
• i=3：表示前3个物品（考虑所有物品）

所以要想考虑所有的物品，就需要从i=0到i=n，一共n+1行。

2.

没有像下面的代码一样初始化第一行。

为什么不需要初始化第一行呢？

主要原因在于dp[i][j] 表示前i个物品（i从0到n）在容量j下的最大价值。所以第一行也就是dp[0][j]这一行，但这一行永远都是0，因为第一行表示前0个物品，也就是没有物品的情况，肯定是0.

3.

为什么是j<v[i-1]而不是像下面的代码一样是j<weight[i]？

还是dp数组初始化的不一样。

1） if(j < v[i-1]) { // 放不下第i个物品 dp[i][j] = dp[i-1][j]; }

因为数组下标是从0开始的，所以相当于是放不下第i个物品，即第一个物品的时候，执行下面的语句。

2）if(j < v[i]) { // 放不下第i+1个物品 dp[i][j] = dp[i-1][j]; }

因为数组下标是从0开始的，所以相当于放不下第二个物品的时候，执行下面的语句。

为什么二者连逻辑也不一样呢？

因为1）初始化的第一行是前0个物品，没有初始化第一个物品。而2）初始化的第一行是第一个物品，所以不需要在处理第一个物品是否能放下的问题了。

上述是新类型的代码，下面是完全和“携带研究材料”题目的dp数组表示完全一样，代码完全一样:

#include<stdio.h> #include<stdlib.h> int max(int a,int b){ if(a>b){ return a; }else{ return b; } } int main() { int q; // 行李箱空间 scanf("%d",&q); int n; // 物品数量 scanf("%d",&n); int i,j; int* v=(int *)malloc(n*sizeof(int)); // 物品体积 for(i=0;i<n;i++){ scanf("%d",&v[i]); } // dp[i][j] 表示前i+1个物品（索引0到i）在容量j下的最大体积 int** dp=(int **)malloc(n*sizeof(int*)); // 只需要n行，因为i从0到n-1 for(i=0;i<n;i++){ dp[i]=(int *)malloc((q+1)*sizeof(int)); for(j=0;j<=q;j++){ dp[i][j]=0; // 初始化 } } // 初始化第一行（i=0，即只考虑第1个物品，索引0） for(j=v[0]; j<=q; j++){ dp[0][j] = v[0]; // 容量足够时，可以放入第一个物品 } // 注意：当j<v[0]时，dp[0][j]已经是0（初始化时设置） // 动态规划 for(i=1; i<n; i++){ // i从1到n-1，表示考虑物品0到i for(j=0; j<=q; j++){ // j从0到q if(j < v[i]){ // 当前容量小于第i+1个物品的体积 dp[i][j] = dp[i-1][j]; // 不选当前物品 }else{ // 选或不选当前物品，取最大值 dp[i][j] = max(dp[i-1][j], dp[i-1][j - v[i]] + v[i]); } } } // 输出最小剩余空间：总容量 - 最大可装入体积 // dp[n-1][q] 表示考虑所有n个物品时能装入的最大体积 printf("%d\n", q - dp[n-1][q]); // 释放内存 for(i=0;i<n;i++){ free(dp[i]); } free(dp); free(v); return 0; }

二.滚动数组(一维)实现01背包

背包最大重量为6。

物品为：

问背包能背的物品最大价值是多少？

对于背包问题其实状态都是可以压缩的。

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实如果把dp[i-1]那一层拷贝到dp[i]上，表达式就可以写成dp[i][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i]);与其把dp[i-1]这一层拷贝到dp[i]上，不如用一个一维数组，只用dp[j]（也可以理解为滚动数组，因为是将上一层拷贝到这一层，然后覆盖着一层，下一次再继续按上述步骤，就像滚动一样）。

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

下面再以动规五部曲解析一下滚动数组：

1.确定dp数组定义及下标含义

dp[j]表示容量为j的背包，所背的物品价值最大是dp[j]。

2.确定递推公式

二维dp数组的递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

因为是将上一行的值先拷贝到这一行，所以递推公式就可以写成dp[i][j]=max(dp[i][j],dp[i][j-weight[i]]+value[i]);所以就可以将i这个维度去掉，直接变成一维数组。

为什么可以将维度i去掉？

关键原因：当我们按特定顺序更新时，一维数组中的值在不同时刻代表二维数组的不同行。

或者是不用拷贝的观点，直接分析一维数组的定义来确定递推公式：此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，容量为j的背包所背的最大价值；一个是取dp[j - weight[i]] + value[i]，即放物品i，但后面加上了物品i的价值，所以前面的背包容量就应该减去物品i的容量，因为已经把物品i放上背包了，所以递归公式为：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])；

3.如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包，所背的物品价值最大为dp[j]，可以直接就求出dp[0]=0，因为背包容量为0所背的物品的最大价值就是0。

那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？

看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。因为我们要求的是最大值，如果我们初始化的值比算出来的值还大，那最后结果就会是我初始化的值，这肯定不对。所以可以直接将所有的都初始化为0.

4.一维dp数组遍历顺序

这里和二维数组遍历背包顺序是不一样的！！！

这里遍历背包是逆序遍历，是为了保证物品i只被放入一次。因为一旦正序遍历，那么物品0就会被重复放入多次。

举例子解析一下：

物品0: 重量1, 价值15
物品1: 重量3, 价值20  
物品2: 重量4, 价值30

如果正序遍历,因为是外层循环是遍历物品，所以一开始是将物品0放入有着所有容量大小的背包中，只考虑物品0.

dp[1] =max(dp[1],dp[1 - weight[0]] + value[0] )= 15

dp[2] = max(dp[2],dp[2 - weight[0]] + value[0]) = dp[1]+value[0]=30

因为先考虑了将物品0放入背包中了，所以正序遍历的时候，dp[1]已经有值了，所以这层式子表示将物品0放入容量为2的背包中的最大价值是30，意味着物品0被放入了两次，所以肯定不能正序遍历。

为什么倒序遍历，就可以保证物品只放入一次呢？

因为根据上述，倒序会保证dp[1]还没有被计算，还保持初始值，所以这样计算出来的肯定是正确的。下面详细计算一下……

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）将物品0放入容量为2的背包中的最大价值。

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

或者是根据滚动数组的拷贝和覆盖解析一下为什么要倒序……

一开始先计算完物品0放在所有容量背包中的处理情况，可以得到物品0在不同容量中的所有价值

因为我们之前说可以解释为上一层数值拷贝到当前层，再进行后面的计算。但是如果正序，就会造成计算的时候，如果前面一种物品满足两种容量下的背包的时候，就会重复计算，造成一种物品被装两次，这正如上述我们得出的结论一样。

#include <stdio.h> #include <stdlib.h> int max(int a, int b) { return a > b ? a : b; } int main() { int M, N; // 读取 M 和 N scanf("%d %d", &M, &N); // 动态分配数组 int *costs = (int*)malloc(M * sizeof(int)); int *values = (int*)malloc(M * sizeof(int)); int *dp = (int*)malloc((N + 1) * sizeof(int)); if (costs == NULL || values == NULL || dp == NULL) { return 1; } // 读取成本 for (int i = 0; i < M; i++) { scanf("%d", &costs[i]); } // 读取价值 for (int j = 0; j < M; j++) { scanf("%d", &values[j]); } // 初始化dp数组为0 for (int i = 0; i <= N; i++) { dp[i] = 0; } // 外层循环遍历每个类型的研究材料 for (int i = 0; i < M; ++i) { // 内层循环从 N 空间逐渐减少到当前研究材料所占空间 for (int j = N; j >= costs[i]; j--) { // 考虑当前研究材料选择和不选择的情况，选择最大值 dp[j] = max(dp[j], dp[j - costs[i]] + values[i]); } } // 输出dp[N]，即在给定 N 行李空间可以携带的研究材料最大价值 printf("%d\n", dp[N]); // 释放内存 free(costs); free(values); free(dp); return 0; }

三.例题：装箱问题

利用上述滚动一维数组解析上述问题。

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积。

现在从 n 个物品中，任取若干个装入箱内（也可以不取），使箱子的剩余空间最小。输出这个最小值。

输入格式

第一行共一个整数 V，表示箱子容量。

第二行共一个整数 n，表示物品总数。

接下来 n 行，每行有一个正整数，表示第 i 个物品的体积。

输出格式

• 共一行一个整数，表示箱子最小剩余空间。

输入 24 6 8 3 12 7 9 7 输出 0 说明/提示 对于 100% 数据，满足 0<n≤30，1≤V≤20000。

#include <stdio.h> #include <stdlib.h> // 定义max函数 int max(int a, int b) { return a > b ? a : b; } int main() { int v; scanf("%d", &v); // 分配dp数组，需要v+1个元素（0到v） int *dp = (int *)malloc((v + 1) * sizeof(int)); int n; scanf("%d", &n); // 分配a数组 int *a = (int *)malloc(n * sizeof(int)); int i, j; // 读取数组元素 for(i = 0; i < n; i++) { scanf("%d", &a[i]); } // 初始化dp数组，容量为i的背包最大价值为0 for(i = 0; i <= v; i++) { dp[i] = 0; } // 0-1背包动态规划 for(i = 0; i < n; i++) { for(j = v; j >= a[i]; j--) { dp[j] = max(dp[j], dp[j - a[i]] + a[i]); } } // 输出结果 if(dp[v] == v) { printf("0\n"); } else if(dp[v] < v) { printf("%d\n", (v - dp[v])); } // 释放内存 free(dp); free(a); return 0; }

上述代码完全就是根据滚动数组的代码逻辑来写的。

但是特别重要的是，就是要学会转换变量。因为上述题目要求装完物品之后，箱子最小剩余空间。没要求最大价值等与价值有关的问题。所以进行转换。因为之前要求的是最大价值，所以就可以考虑也设置价值，只不过重量和价值相等，那么，当价值最大的时候，也就是空间利用最多的时候，因为我们将容量和价值等同了。所以values[i]=weight[i]=a[i](我上面代码中设置的变量)，就可以将原代码中的values[i]转换成a[i]。然后，在后面的输出结果时需要变换一下，其他都不需要变。

dp[j]表示的是容量为j的背包，最大价值是dp[i]，也可以称作填充的最大容量。最后肯定可能不能全部填充满。所以按上述写代码，完全符合题目要求。