动态规划：01 背包问题详解

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

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

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

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

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

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

// 固定物品 i，计算它在所有容量 j 下的 dp 值
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= bagweight; j++) {
        // ...
    }
}

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

// 固定容量 j，计算所有物品在这个容量下的 dp 值
for (int j = 0; j <= bagweight; j++) {
    for (int i = 1; i <= n; i++) {
        // ...
    }
}

根据上述计算过程，都满足上述条件，计算 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;
}

例题二：砝码称重

题目描述

你有一架天平和 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 个砝码总重不超过 10^5。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <math.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。

情况 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

注意事项！！！ 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，10g 砝码的数量。 第二行输入 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 组的情况单独拿出来。

解析一下下面代码：

c
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]);
        }
    }
}

观察上述两个代码，区别在于上述：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 开始的，所以相当于放不下第二个物品的时候，执行下面的语句。

上述是新类型的代码，下面是完全和'携带研究材料'题目的 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]=ai，就可以将原代码中的 values[i] 转换成 a[i]。然后，在后面的输出结果时需要变换一下，其他都不需要变。

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