C语言动态规划解决0-1背包问题

动态规划（Dynamic Programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，它能够将问题分解为相互独立的子问题，并将子问题的解存储起来，以便下次需要时直接使用，从而减少计算量，提高效率。最经典的例子就是0-1背包问题。

0-1背包问题描述：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，选取若干种物品，使得物品的总价值最大。其中，每种物品只能选择一次或不选择。
 

基本思路

用子问题定义状态：f[i][c] 表示前 i 件物品放入一个容量为 c 的背包可以获得的最大价值。第 i 件物品的重量是 wi，价值是 vi，则其状态转移方程是：

f[i][c] = max(f[i-1][c], f[i-1][c-wi] + vi)

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。分析子问题“将前 i 件物品放入容量为 c 的背包中”，考虑第 i 件物品放或不放入背包，可以转化为一个只牵扯前 i-1 件物品的问题：如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入容量为 c 的背包中”，价值为 f[i-1][c]；如果放第 i 件物品，那么问题就转化为“前 i-1 件物品放入剩下的容量为 c-wi 的背包中”，此时能获得的最大价值就是 f[i-1][c-wi] 再加上通过放入第 i 件物品获得的价值 vi。所以按照这个方程递推完毕后，最终的答案一定是 f[i][c]。

示例程序

#include <stdio.h>
 
#define max(a, b) a > b ? a : b
 
int knapsack(int weights[], int values[], int capacity, int n) {
    // f[i][c] 表示在前i个物品中选择若干个物品放入容量为c的背包中所能获得的最大价值
    int f[n + 1][capacity + 1];
 
    for (int i = 0; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            if (i == 0 || c == 0) {
                // 前0个物品，或者容量为0，价值也为0
                f[i][c] = 0;
            } else if (c < weights[i-1]) {
                // i表示前i个物品，所以第i个物品的重量是 weights[i-1]，对应前面公式中的 wi
                // 遍历到当前容量c小于当前物品的重量，无法放入该物品，保持背包现状
                // 即：上一轮遍历物品的循环中同样数量物品的最大价值，所以是 f[i-1][c]
                f[i][c] = f[i-1][c];
            } else {
                // i表示前i个物品，所以第i个物品的价值是 values[i-1]，对应前面公式中的 vi
                // 可以放入，判断放入该物品是否能使背包中物品价值最大
                // 如果放入，可能需要腾出背包中同样重量的物品，所以是 f[i-1][c-weights[i-1]]
                // 然后 f[i-1][c-weights[i-1]] + values[i-1] 得到放入该物品后的价值
                // 不放入该物品（保持背包现状），与放入该物品，取两者中的最大值
                f[i][c] = max(f[i-1][c], f[i-1][c - weights[i-1]] + values[i-1]);
            }
        }
    }
 
    // 输出动态规划数组中的值，显示规划过程，用于分析理解
    for (int i = 0; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            printf("%d", f[i][c]);
            if (c < capacity) {
                printf(", ");
            }
        }
        printf("\n");
    }
 
    return f[n][capacity];
}
 
int main() {
    // 物品重量
    int weights[] = {2, 2, 1, 3};
    // 物品价值
    int values[] = {4, 2, 3, 6};
    // 背包的容量限制
    int capacity = 3;
    // 物品数量
    int n = sizeof(values) / sizeof(values[0]);
 
    printf("最大价值: %d\n", knapsack(weights, values, capacity, n));
 
    return 0;
}

 

分析过程

程序输出如下：

0, 0, 0, 0 
0, 0, 4, 4 
0, 0, 4, 4 
0, 3, 4, 7 
0, 3, 4, 7 
最大价值: 7

上面输出的前5行是动态规划数组中的内容，回顾一下程序中的这行注释内容：f[i][c] 表示在前 i 个物品中选择若干个物品放入容量为 c 的背包中所能获得的最大价值。咱们的示例数据中，一共有4个物品，背包的容量为3，所以数组的大小是5x4（为什么维度比物品数和背包容量都大1？请带着这个问题往下看）。现在开始逐行分析数组中的数据：

第1行：不选择任何物品，所以价值都为0。为方便阅读，避免频繁上下滑动屏幕，后续会复制所需查看的输出：

0, 0, 0, 0

第2行：选择前1个物品，该物品重量为2，价值为4。从0-3遍历背包容量，依次尝试放入该物品，遍历过程中，容量为0都不能放入，所以第1列数据永远为0。容量为1不能放入当前物品，容量为2和3可以放入，且是第1个物品，可直接放入背包，得到背包中物品的价值就是该物品的价值4。

0, 0, 0, 0 
0, 0, 4, 4

第3行：选择前2个物品，问题转变为在前1个物品的基础上，放入第2个物品。根据前面的子问题说明：考虑第 i 件物品放或不放入背包，可以转化为一个只牵扯前 i-1 件物品的问题：如果不放第 i 件物品，那么问题就转化为“前 i-1 件物品放入容量为 c 的背包中”，价值为 f[i-1][c]；如果放第 i 件物品，那么问题就转化为“前 i-1 件物品放入剩下的容量为 c-wi 的背包中”，此时能获得的最大价值就是 f[i-1][c-wi] 再加上通过放入第 i 件物品获得的价值 vi。第2个物品的重量为2，价值为2。和前一个物品一样，容量为2和3可以放入，但背包剩余容量不够，需要置换前面放入的物品。如果放入该物品，置换出原价值为4的物品，所能得到的价值为2，小于背包中物品现有的价值4，因此不放入该物品，背包中物品价值仍为4。

0, 0, 0, 0 
0, 0, 4, 4 
0, 0, 4, 4

第4行：选择前3个物品，问题转变为在前2个物品的基础上，放入第3个物品。第3个物品的重量为1，价值为3。从0-3遍历背包容量，容量为1时，背包中没有物品，直接放入，背包中物品价值为该物品的价值3；容量为2时，由于已经放入物品，价值为4，该物品可以放入背包，但背包剩余容量不够，需要置换前面放入的物品，置换后所能得到的价值为2，小于背包中物品现有的价值4，因此不放入该物品，背包中物品价值仍为4；容量为3时，背包中有物品，也有剩余容量，根据前面的方程 f[i][c] = max(f[i-1][c], f[i-1][c-wi] + vi) 计算 f[3][3] = max(f[2][3], f[2][3-1]+3)，即不放入该物品时的价值 f[2][3] = 4，与放入该物品时的价值 f[2][2]+3 = 7，因此放入该物品，背包中物品价值最大为7。

0, 0, 0, 0 
0, 0, 4, 4 
0, 0, 4, 4 
0, 3, 4, 7

第5行：选择前4个物品，问题转变为在前3个物品的基础上，放入第4个物品。第4个物品的重量为3，价值为6。从0-3遍历背包容量，只有容量为3时可以放入该物品，如果放入该物品，置换出背包中容量为3的物品，f[i-1][c-wi] + vi = f[3][0]+6 = 6，小于不放入该物品时背包中的物品价值7，因此不放入该物品。

0, 0, 0, 0 
0, 0, 4, 4 
0, 0, 4, 4 
0, 3, 4, 7 
0, 3, 4, 7

最终的答案是 f[4][3]，程序输出最大价值: 7。