一、基础01背包（二维版本）

问题模型

有 $n$ 个物品，背包容量为 $m$。第 $i$ 个物品重量为 $w[i]$，价值为 $v[i]$。每个物品只能选一次，求背包能装下的最大价值。

状态定义

dp[i][j]：考虑前 $i$ 个物品，背包体积为 $j$ 时，能获得的最大价值。

转移方程

• 不选第 $i$ 个物品：dp[i][j] = dp[i-1][j]
• 选第 $i$ 个物品（仅当 $j \geq w[i]$）：dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, w[N], v[N];
int dp[40][210]; // dp[i][j]：前i个物品，体积j时的最大价值

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    // 基础二维01背包
    for (int i = 1; i <= n; i++) { // 枚举前i个物品
        for (int j = 0; j <= m; j++) { // 枚举背包体积
            // 不选第i个物品
            dp[i][j] = dp[i-1][j];
            // 选第i个物品（如果体积足够）
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[n][m] << endl; // 输出最大价值
    return 0;
}

二、空间优化：一维版本

优化思路

由于 dp[i][j] 仅依赖 dp[i-1][...]（上一行的数据），因此可以用一维数组滚动更新，节省空间。

注意事项

体积循环必须倒序（从 $m$ 到 $w[i]$），防止同一物品被重复选择（避免覆盖上一行的 dp[j - w[i]]）。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, w[N], v[N];
int dp[210]; // 优化为一维：dp[j]表示体积j时的最大价值

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    // 空间优化一维版
    for (int i = 1; i <= n; i++) { // 枚举物品
        for (int j = m; j >= w[i]; j--) { // 倒序枚举体积！
            // 不选：dp[j]（原值，即上一行的结果）
            // 选：dp[j - w[i]] + v[i]
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

三、变体1：“至少容量V”的最小花费

问题模型

购买饮料，第 $i$ 瓶饮料容量为 $v[i]$，价格为 $w[i]$。要求总容量至少为 $V$，求最少花费。

状态定义

dp[i][j]：考虑前 $i$ 个物品，总容量至少为 $j$ 时，能获得的最小花费。

转移方程

• 不买第 $i$ 瓶：dp[i][j] = dp[i-1][j]
• 买第 $i$ 瓶：
  • 若 $j \leq v[i]$：买这一瓶就满足，花费为 $w[i]$
  • 若 $j > v[i]$：需要前 $i-1$ 瓶至少满足 $j - v[i]$，花费为 dp[i-1][j - v[i]] + w[i]

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int dp[510][2100], w[510], v[510], V, n;
// dp[i][j]：前i个物品，容量至少j时的最小花费

signed main() {
    memset(dp, 0x3f, sizeof dp); // 初始化为无穷大（求最小值）
    dp[0][0] = 0; // 边界：0个物品，容量至少0，花费0
    cin >> n >> V;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++) { // 枚举物品
        for (int j = 0; j <= V; j++) { // 枚举“至少容量j”
            // 不买第i个
            dp[i][j] = dp[i-1][j];
            // 买第i个
            if (j > v[i]) {
                dp[i][j] = min(dp[i][j], dp[i-1][j - v[i]] + w[i]);
            } else {
                dp[i][j] = min(dp[i][j], w[i]);
            }
        }
    }

    if (dp[n][V] == INF) cout << "no solution";
    else cout << dp[n][V];
    return 0;
}

四、变体2：求“可达到的体积集合”

问题模型

给定 $n$ 个物品，每个体积为 $a[i]$。求所有能被恰好凑出的体积，并统计个数。

状态定义

dp[i][j]：考虑前 $i$ 个物品，背包体积为 $j$ 时，能获得的最大价值（此处“价值”等于“体积”，即若 dp[n][j] == j，说明体积 $j$ 可被凑出）。

转移方程

与基础01背包一致：

• 不选：dp[i][j] = dp[i-1][j]
• 选（$j \geq a[i]$）：dp[i][j] = max(dp[i-1][j], dp[i-1][j - a[i]] + a[i])

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[105], ans, dp[101][100001], V;
// dp[i][j]：前i个物品，体积j时的最大价值（价值=体积）

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        V += a[i]; // 总体积上限
    }

    for (int i = 1; i <= n; i++) { // 枚举物品
        for (int j = 0; j <= V; j++) { // 枚举体积
            if (j >= a[i]) {
                // 选或不选，取最大（价值=体积）
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - a[i]] + a[i]);
            } else {
                dp[i][j] = dp[i-1][j]; // 不选
            }
        }
    }

    // 统计所有能凑出的体积（dp[n][i] == i 说明i可被凑出）
    for (int i = 1; i <= V; i++) {
        if (dp[n][i] == i) ans++;
    }
    cout << ans << endl;
    for (int i = 1; i <= V; i++) {
        if (dp[n][i] == i) cout << i << " ";
    }
    return 0;
}