背包问题包括0-1背包问题、完全背包问题、部分背包问题以及其他变体。其中，部分背包问题最简单，可以用贪心法求解，而其他背包问题往往需要动态规划。本文主要来自《背包问题九讲》。我选择了相对简单的0-1背包挑战和完整背包挑战来总结。同时提供了应用代码。如有错误请指正。本文的代码在这里。

1 部分背包问题

部分背包问题描述： 有 N 件物品，背包容量为 C，第 i 件物品的重量为 w[i]，值为 v[ i ]。找出哪些物品可以装在背包中以最大化总价值。请注意，您不需要在此处加载整个项目，您只能加载项目的一部分。

解决方案： 背包问题的一部分通常使用贪心算法来解决。首先计算每个商品单位的单位重量单位值v[i]/w[i]，然后从最大的单位开始，然后取第二个值的单位。直到背包满为止。按照这种贪心策略，你得到的一定是最大的总价值。这个比较简单，所以应用代码就省略了。

2 0-1背包问题

0-1背包问题描述

有N件物品，背包容量为C，第i件物品的重量为w[i]，值为v[i ]。找出哪些物品可以装在背包中以最大化总价值。注意物品可以拿，也可以不拿，这正是0-1的意思。背包问题的一部分可以被认为是获取金粉，而 0-1 背包问题是获取金块，其中一个是可整除的，另一个是不可分割的。

分析

这是最基本的背包问题。其特点是：每种类型只有一项，可以放也可以不放。用子任务定义状态：即f[i][w]表示将前i件物品放入容量为c的背包中可以获得的最大值。那么状态转移方程为：

f[i][c] = max{f[i-1][c], f[i-1][c-w[i]]+v[i]} 
复制代码

这个方程非常重要，基本上所有与背包相关的方程都是由它推导出来的。所以有必要详细解释一下： 将第 i 件物品放入体积为 c 的背包中 对于这个子问题，如果只有第 i 件物品的策略（放或不放）是这样就可以转化陷入仅涉及前 i-1 单元的问题。

• 如果不放入第i件物品，问题转化为：将第i-1件物品放入容量为v的背包中，值为f[ i -1][c]；
• 如果放入第i个物品，问题就变了将第i-1个物品放入剩余背包容积c-w[i]。目前你可以得到的最大值是f[i-1][c-w[i]]加上放置第i个物品得到的值v[i]。

空间复杂度优化

上述方法的时间和空间复杂度均为O(CN)。时间复杂度应该不再优化，但是空间复杂度可以优化到O(N)。因为计算 f[i][c] 时我们只需要使用 f[i-1][c] 和 f-w[i-1][ i]] ，所以它们的值可以通过一维数组来存储。这里使用的一个小技巧是从 c=C...0 开始，这样就可以了。 f[c]、

、

c-w[i]] 保证与 f[i-1][c-w[i]] 一起存储。请注意，这不能从 c=0...C 导出，因为这会导致 f[c-w[i]] ] [ c-w[i]] 而不是 f[i-1][c-w[i]。可以在此处优化下限。事实上，你只需要从c=C...w[i]开始，这有助于避免不必要的计算。伪代码如下：

for i=0..N-1
    for c=C..w[i]
        f[c]=max{f[c],f[c-w[i]]+v[i]};
复制代码

最终实现代码如下：

int knap01(int N, int C, int w[], int v[])
{
    int *f = (int *)calloc(sizeof(int), C+1);
    int i, c;

    for (i = 0; i < N; i++) {
        for (c = C; c >= w[i]; c--) {
            f[c] = max(f[c], f[c-w[i]] + v[i]);
        }
        printf("%d: ", i+1);
        printIntArray(f, C+1); // 打印f数组
    }
    return f[C];
}
复制代码

测试结果如下，即如果背包容量为10，则第1、第2项（索引从0开始） ，总权重为4+5=9，最大值为5+6=11。

参数：
w = [3, 4, 5] //物品重量列表
v = [4, 5, 6] //物品价值列表
C = 10

结果（打印数组f，i为选择的物品索引，c为背包重量，值为背包物品价值）：
         
i/c 0 1 2 3 4 5 6 7 8 9 10
 0: 0 0 0 4 4 4 4 4 4 4 4 
 1: 0 0 0 4 5 5 5 9 9 9 9 
 2: 0 0 0 4 5 6 6 9 10 11 11 

KNap01 max: 11
复制代码

初始化细节

在我们看到的寻找最优解的背包问题的问题中，有两种不同的提问方式。有些问题需要在背包完全装满的情况下得到最优解，而另一些问题则不需要背包装满。区分这两个问题的一种实现方法是改变初始化期间的间隙。

如果这是第一道要求背包精确填充的题，那么初始化时，除了f[0]为0之外，其他f[1..C]所有值都是 -∞ ，可以保证最终的f[N]是刚好装满背包的最优解。如果没有要求填满背包，但希望价格尽可能高，那么初始化时就应该将所有f[0..C]设置为0。

为什么呢？这可以这样理解：初始化后的f数组实际上是一个合法的状态，没有物品可以被背包。如果背包必须被精确填充，那么只有容量为0的背包才能被值为0的东西“精确填充”。对于其他容量的背包没有合法的解决方案，它们处于未定义状态，并且它们的值都应该是-∞。如果背包不需要装东西，那么任何容量的背包都有一个合法的解决方案“什么都不装”。这个解的值为0，所以初始状态值都是0。

3 完成背包问题

问题描述

有一个类型为N的物品和一个容量为C的背包。每个物品有无限数量的可用物品。第 i 个元素的权重为 w[i]，值为 v[i]。找出背包里应该装哪些物品，使这些物品的总重量不超过背包的容量，且总价值最大。项目不能仅部分完成。

基本思想

这个问题与0-1背包问题非常相似，只不过每件物品的件数是无限的。这意味着，从每一项来看，相关策略不再是取或不取两种类型，而是有取0项、取1项、取2项等几种类型。仍然遵循与求解01背包时相同的思路，令f[i][c]为容量为c的背包中可以放入的第i个物品的最大重量。但是，您可以用不同的策略为每个单元编写状态转移方程，例如如下：

f[i][c] = max{f[i-1][c-k*w[i]]+ k*w[i]| 0<=k*w[i]<=c }
复制代码

它具有与 0-1 背包问题相同的 O(CN) 状态来求解，但每个状态都需要时间来求解。状态不再恒定。 ，求解状态 f[i][c] 的时间为 O(c/w[i])，总复杂度可以视为 CN*Σ (c/w[i ])) 相对较大。实现代码如下：

/*
 * 完全背包问题
 */
int knapComplete(int N, int C, int w[], int v[])
{
    int *f = (int *)calloc(sizeof(int), C+1);
    int i, c, k;
    for (i = 0; i < N; i++) {
        for (c = C; c >= 0; c--) {
            for (k = 0; k <= c/w[i]; k++) {
                f[c] = max(f[c], f[c-k*w[i]] + k*v[i]);
            }
        }
        printf("%d: ", i+1);
        printIntArray(f, C+1);
    }
    return f[C];
}
复制代码

以0-1背包问题为例，程序运行结果如下。最大值为13，即选择权重为3的两项和权重为4的一项，合计值最大，为 4*2 + 5 = 13。

i/c: 0 1 2 3 4 5 6 7 8 9 10
0:   0 0 0 4 4 4 8 8 8 12 12 
1:   0 0 0 4 5 5 8 9 10 12 13 
2:   0 0 0 4 5 6 8 9 10 12 13 

KNapComplete max: 13
复制代码

将0-1转化为背包问题

由于背包问题01是最基本的背包问题，所以我们可以考虑将整个背包问题转化为背包问题01。最简单的想法是考虑第i个单元最多可以选择C/w[i]个，这样第i个单元就可以转换为C/w[i ]。 件 恒定成本和价值的物品，然后解决这个01背包问题。这根本没有提高主要思想的时间复杂度，但毕竟它给了我们将整个背包问题转化为背包问题01：将一项物品拆分为多项的想法。

更高效的转换方法如下：将第 i 项拆分为 w[i]*2^k 和w[i]*2^k 中的多个元素其中 k 匹配 w[i]*2^k