背包问题核心模型课堂笔记

一、01背包：每个物品只能选一次

1. 基础模型：求最大价值

状态定义：

• dp[i][j]：前 i 个物品可选，背包承重上限为 j 时的最大价值
• w[i]：第 i 个物品的重量；v[i]：第 i 个物品的价值

状态转移方程：

if (j >= w[i])  // 能装下第i个物品，选或不选取最大值
    dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
else  // 装不下，只能不选
    dp[i][j] = dp[i-1][j];

初始化：dp[0][j] = 0（无物品时价值为0）

2. 进阶模型：求最大价值的方案数

新增状态定义：

• f[i][j]：前 i 个物品可选，背包承重上限为 j 时，取得最大价值的方案数

状态转移逻辑：

if (j < w[i]) {  // 装不下，方案数继承自不选i的情况
    dp[i][j] = dp[i-1][j];
    f[i][j] = f[i-1][j];
} else {
    if (dp[i-1][j] < dp[i-1][j - w[i]] + v[i]) {  // 选i更优，方案数继承自选i
        dp[i][j] = dp[i-1][j - w[i]] + v[i];
        f[i][j] = f[i-1][j - w[i]];
    } else if (dp[i-1][j] > dp[i-1][j - w[i]] + v[i]) {  // 不选i更优，方案数继承自不选i
        dp[i][j] = dp[i-1][j];
        f[i][j] = f[i-1][j];
    } else {  // 选与不选价值相同，方案数相加
        dp[i][j] = dp[i-1][j];
        f[i][j] = f[i-1][j] + f[i-1][j - w[i]];
    }
}

初始化：

• dp[0][j] = 0；f[0][0] = 1（0个物品、承重0时，价值0，方案数1）
• 若题目要求方案数取模，需在加法处取模

二、完全背包：每个物品可选无限次

1. 基础模型：求最大价值

状态定义：同01背包（dp[i][j]：前 i 个物品，承重 j 的最大价值）

状态转移方程（与01背包唯一区别：选i时用dp[i][j - w[i]]）：

if (j >= w[i])  // 选i时可重复选，因此用dp[i][j - w[i]]
    dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i]);
else  // 装不下，继承不选i的情况
    dp[i][j] = dp[i-1][j];

2. 进阶模型：求最大价值的方案数

状态转移逻辑：

if (j < w[i]) {  // 装不下，方案数继承自不选i
    dp[i][j] = dp[i-1][j];
    f[i][j] = f[i-1][j];
} else {
    if (dp[i-1][j] < dp[i][j - w[i]] + v[i]) {  // 选i更优，方案数继承自选i
        dp[i][j] = dp[i][j - w[i]] + v[i];
        f[i][j] = f[i][j - w[i]];
    } else if (dp[i-1][j] > dp[i][j - w[i]] + v[i]) {  // 不选i更优，方案数继承自不选i
        dp[i][j] = dp[i-1][j];
        f[i][j] = f[i-1][j];
    } else {  // 选与不选价值相同，方案数相加（选i时用f[i][j - w[i]]）
        dp[i][j] = dp[i-1][j];
        f[i][j] = f[i-1][j] + f[i][j - w[i]];
    }
}

三、背包变形：价值达标，求最小花费

问题场景：给定物品重量 w[i]、价值 v[i]，要求总价值恰好达到 m，求最小总重量

状态定义：

• dp[i][j]：前 i 个物品可选，总价值恰好为 j 时的最小重量

状态转移方程（类似完全背包，01背包则改为dp[i-1][j - v[i]]）：

memset(dp, 0x3f, sizeof dp);  // 初始化为无穷大，表示“不可达”
dp[i][0] = 0;  // 价值为0时，重量为0（前i个物品都不选）

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (j >= v[i])  // 能选第i个物品，取最小重量
            dp[i][j] = min(dp[i-1][j], dp[i][j - v[i]] + w[i]);
        else  // 不能选，继承不选i的情况
            dp[i][j] = dp[i-1][j];
    }
}
// 最终答案：dp[n][m]（若仍为无穷大，说明无法达到价值m）

核心对比速查表： | 背包类型 | 选i时的状态转移核心 | 典型问法 | |----------|----------------------|----------| | 01背包 | dp[i-1][j-w[i]]+v[i] | 最大价值/方案数 | | 完全背包 | dp[i][j-w[i]]+v[i] | 最大价值/方案数 | | 最小花费 | dp[i][j-v[i]]+w[i] | 价值达标，最小重量 |