动态规划再进阶：背包问题三兄弟

背包问题，可以说是动态规划里最经典的入门题了。我当年学DP的时候，就是靠背包问题真正开窍的。今天咱们一口气把三个背包问题讲透——0-1背包、完全背包、多重背包。

说白了，这三个问题就是同一个框架下的变种。你只要理解了最基础的0-1背包，后面两个就是改一两行代码的事。

0-1背包问题：每个物品只能拿一次

先看最经典的场景：你有一个容量为W的背包，有n个物品，每个物品有重量w[i]和价值v[i]。每个物品要么拿，要么不拿——这就是"0-1"的含义。

我刚开始学的时候，总想着用贪心去解，结果发现贪心根本不行。为什么？因为贪心只看局部最优，但背包问题需要全局权衡。

核心思路是这样的：

• 定义dp[i][j]：前i个物品，背包容量为j时，能装的最大价值
• 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
• 前者是不拿第i个物品，后者是拿

嗯，这里要注意：拿的前提是j >= w[i]。

// 0-1背包标准写法
int knapsack01(int W, int n, int w[], int v[]) {
    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], 
                               dp[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return dp[n][W];
}

我个人习惯用一维数组优化空间。你想想看，dp[i][j]只依赖dp[i-1][...]，那我们可以只保留一行，从后往前更新。

// 空间优化版
int knapsack01_opt(int W, int n, int w[], int v[]) {
    int dp[W+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i < n; i++) {
        // 必须从大到小遍历！
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    return dp[W];
}

完全背包问题：每个物品可以拿无限次

完全背包和0-1背包的唯一区别：每个物品可以拿任意多次。你想想看，这会导致什么变化？

状态转移方程变成了：dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

注意看，第二个参数从dp[i-1]变成了dp[i]。这意味着：当你决定拿第i个物品时，你还可以继续拿第i个物品——因为可以重复拿。

// 完全背包
int completeKnapsack(int W, int n, int w[], int v[]) {
    int dp[W+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i < n; i++) {
        // 必须从小到大遍历！
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    return dp[W];
}

你看，代码和0-1背包几乎一样，就内层循环的方向反了。0-1背包从大到小，完全背包从小到大。这个区别，我建议你死记硬背下来。

多重背包问题：每个物品有数量限制

多重背包介于两者之间：每个物品最多拿k[i]次。最朴素的做法就是拆成0-1背包——把每个物品的k个副本都当成独立物品。

但这样效率太低了。如果k很大，物品数量会爆炸。我记得有一次处理一个数据，k[i]最大是10^5，直接拆的话内存都扛不住。

优化方案是二进制拆分法。把k拆成1, 2, 4, 8, ... 2^m, 剩余部分。这样只需要log(k)个物品就能表示0到k的所有组合。

// 多重背包 - 二进制优化
void multipleKnapsack(int W, int n, int w[], int v[], int k[]) {
    int dp[W+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 0; i < n; i++) {
        int count = k[i];
        // 二进制拆分
        for (int t = 1; t <= count; t <<= 1) {
            int weight = w[i] * t;
            int value = v[i] * t;
            for (int j = W; j >= weight; j--) {
                dp[j] = max(dp[j], dp[j-weight] + value);
            }
            count -= t;
        }
        // 处理剩余部分
        if (count > 0) {
            int weight = w[i] * count;
            int value = v[i] * count;
            for (int j = W; j >= weight; j--) {
                dp[j] = max(dp[j], dp[j-weight] + value);
            }
        }
    }
}

三种背包对比

问题类型	物品限制	内层遍历方向	时间复杂度
0-1背包	每个最多1次	从大到小	O(nW)
完全背包	无限次	从小到大	O(nW)
多重背包	最多k次	从大到小（二进制优化后）	O(nW log k)

说实话，这三个问题搞懂了，动态规划就算是入门了。我在实际项目中遇到过不少变种，比如背包加了个"必须装满"的条件，或者物品有体积和重量两个维度。但万变不离其宗，核心还是这个状态转移框架。

嗯，背包问题就讲到这里。这三个问题你吃透了，动态规划的基本功就算扎实了。代码多写几遍，尤其是那个一维数组的写法，面试时经常考。