一提到动态规划，就一定离不开经典且入门级的“背包问题”，我将用最通俗的语言拆解模型，带你从零学会 DP。

前言

在每次解动规的题目之前，我们必须先理清以下几个问题：

1、明确dp[i] 或dp[i][j] 数组带有下标的实际含义

2、状态转移方程：dp[i]由什么得来，和上一个状态dp[i-1]之间是什么关系

3、初始化dp数组

4、弄清填满dp数组的遍历方式是什么，含义是什么

5、最终要求的结果和dp数组是什么关系

---

一、背包问题

核心场景：有一个背包，最大承重为 W。现在有 n 个物品，每个物品： 重量为weight[i]，价值为value[i]

目标：在不超过背包承重的前提下，求最大能装下的价值

三个背包的唯一区别：物品能不能重复拿

而解决所有背包问题，只有一个核心思路：对于当前背包容量 j，选这个物品 vs 不选这个物品，取价值最大的那个

dp[j] = max( 不选这个物品的价值 , 选这个物品的价值 )

dp[j]的含义：背包容量为j时，能装的最大价值。

1、01背包

特点：每个物品只有 1 个，要么拿，要么不拿（二选一）

(1) 定义状态：dp[ j ] ：此时背包容量为 j ，能装下的最大价值

(2) 转移状态：

对第 i 个物品，只有两种选择：

1、不选，dp[j]保持不变（因为背包容量没变，所以继承上一个物品的结果）

2、选(前提：装得下)   此时的背包容量是已经包括该物品的重量了，是已经装下了 —— >所以需要先腾出这个物品的重量，在上一状态的最大价值的基础上，再加上该物品的价值

dp[j]=dp[j-weight[i]]+value[i]

3、不管选还是不选，对于同一容量j来说，最终取最大价值：dp[j] = max(不选, 选)

(3) 遍历方式：总体来说需要遍历每一个物品 i ，然后对于每个物品来说，需要遍历所有大于自身重量的的背包容量大小，因为只要书包能装得下，都有可能选这个物品，但是需要选择出最佳方案使最终结果的价值最大。

注意：遍历背包容量大小，必须倒序遍历！

（4）最终的结果就是dp[W]:当背包容量为最大承重量W时，此时书包的最大价值

public static void main(String[] args) {
        // 1. 定义一些基本信息
        int maxWeight = 4; // 背包最大承重
        int[] weight = {1, 3, 4};   // 3个物品的重量
        int[] value = {15, 20, 30}; // 3个物品的价值
        
        // 2. 创建dp数组：dp[j] = 容量为j时背包的最大价值
        int[] dp = new int[maxWeight + 1];
        
        // 3. 核心遍历：先物品，再倒序背包容量
        for (int i = 0; i < weight.length; i++) { 
            // 倒序遍历背包容量！防止重复拿
            for (int j = maxWeight; j >= weight[i]; j--) {
                // 核心公式：不选 vs 选，取最大
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println("01背包最大价值：" + dp[maxWeight]);
    }

2、完全背包

特点：每个物品无限多个，可以无限拿

和01背包的唯一区别就是：背包容量 正序遍历（可以重复拿同一个物品）

其他代码完全一样！只需要改一行

public static void main(String[] args) {
        int maxWeight = 4;
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        
        int[] dp = new int[maxWeight + 1];
        
        // 遍历物品
        for (int i = 0; i < weight.length; i++) {
            // 完全背包：正序遍历！唯一区别
            for (int j = weight[i]; j <= maxWeight; j++) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        
        System.out.println("完全背包最大价值：" + dp[maxWeight]);
    }

3、多重背包

特点：每个物品有固定数量（比如 3 个、5 个），只要不超过数量就行

核心逻辑：在 01 背包基础上，里面再加一层数量循环（用于计数）

遍历「当前物品能拿的个数」，0 个、1 个、2 个... 直到上限

public static void main(String[] args) {
        int maxWeight = 5;
        int[] weight = {1, 2};   // 物品重量
        int[] value = {10, 15};  // 物品价值
        int[] count = {3, 2};    // 物品数量：物品1有3个，物品2有2个
        
        int[] dp = new int[maxWeight + 1];
        
        // 遍历物品
        for (int i = 0; i < weight.length; i++) {
            // 倒序遍历（01背包逻辑）
            for (int j = maxWeight; j >= weight[i]; j--) {
                // 加一层：遍历物品能拿的个数（多重背包核心）
                for (int k = 1; k <= count[i] && j >= k * weight[i]; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * weight[i]] + k * value[i]);
                }
            }
        }
        
        System.out.println("多重背包最大价值：" + dp[maxWeight]);
}

---

二、核心困惑点：倒序和正序到底有什么区别？

先记住前提：一维数组 dp[j]代表：背包容量 为 j 时的最大价值

核心本质：

倒序：从大容量往小容量算 → 不会重复用同一个物品（01背包）

正序：从小容量往大容量算 → 会重复使用同一个物品（完全背包）

先举一个例子：假设背包最大容量为4，只有一个物品：重量为1，价值为15

初始 dp=[0,0,0,0,0]

（1）倒序遍历背包容量

遍历该物品（因为只有一个物品，所以只需要遍历一次），并倒序遍历背包容量：

• j=4：dp[4]=max(dp[4],dp[4-1]+15)，因为一开始dp[4]和dp[3]都是0，所以dp[4]=max(0,0+15)=15
• j=3：dp[3]=max(dp[3],dp[3-1]+15)，同理dp[3]=max(0,0+15)=15
• j=2：dp[2]=max(dp[2],dp[2-1]+15)，dp[2]=15
• j=1：dp[1]=max(dp[1],dp[0]+15)，dp[1]=15

这意味着，不管背包容量为多大，最多只能装一个物品，价值为15

（2）正序遍历背包容量

初始还是dp=[0,0,0,0,0]

• j=1：dp[1]=max(dp[1],dp[0]+15)=15
• j=2：dp[2]=max(dp[2],dp[1]+15)=30 -->此时就会很显然的发现，之前dp[1]的时候已经装进去一次了，此时dp[2]又装了一次，明显装了2个物品
• j=3：dp[3]=max(dp[3],dp[2]+15)=45 -->装了3个
• j=4：dp[4]=max(dp[4],dp[3]+15)=60 -->装了4个

相当于可以反复用同一个物品叠加，无限拿

（3）那么多重背包的倒序遍历的逻辑是什么？

多重背包 = 01 背包的升级版，本质还是 “每个物品只能用有限次”，只要不超过给定的数量范围就行，意味着给机会都试试，但最终只取最佳效果，最大价值。所以必须倒序遍历！

---

三、总结

背包类型	物品数量	遍历顺序（背包容量）	核心代码区别
01 背包	1 个	倒序	for(j = maxW; j >= w[i]; j--)
完全背包	无限个	正序	for(j = w[i]; j <= maxW; j++)
多重背包	有限个	倒序 + 数量循环	里面多一层k遍历个数