豆包AI生成

背包 DP 是动态规划最经典入门题，分 01 背包、完全背包、多重背包、分组背包。

状态定义通用思路： dp[j]：背包容量为 j 时，能装的最大价值

---

1. 01 背包（每件物品只能选 0 或 1 次）

题目：n 个物品，每个物品体积 v[i]，价值 w[i]，背包总容量 m，每件最多拿一次，求最大价值。 二维原始版（好理解）

#include <iostream>
using namespace std;
const int N = 1005;
int v[N], w[N];
// dp[i][j]：前i个物品，容量j的最大价值
int dp[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            // 不选第i件
            dp[i][j] = dp[i-1][j];
            // 能选才更新
            if(j >= v[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

✅ 一维优化（常用！），j 倒序遍历，防止重复选

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1005;
int dp[M];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        // 倒序！01背包核心
        for(int j = m; j >= v; j--)
        {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

重点：01 背包 for (j=m; j>=v; j--) 倒序

---

2. 完全背包（物品可以无限选）

物品可以拿无数次，j 正序遍历

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1005;
int dp[M];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int v, w;
        cin >> v >> w;
        // 正序！完全背包核心，可以重复取
        for(int j = v; j <= m; j++)
        {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

对比记忆： 01 背包：倒序，每个物品只用一次 完全背包：正序，物品可以反复选

---

3. 多重背包（每个物品有 s [i] 件）

每个物品最多拿 s 个。

朴素写法（慢，数据小可用）

int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
    int v, w, s;
    cin >> v >> w >> s;
    for(int j = m; j >= v; j--)
    {
        // 枚举取k件
        for(int k = 1; k <= s && k*v <= j; k++)
        {
            dp[j] = max(dp[j], dp[j - k*v] + k*w);
        }
    }
}

二进制优化（推荐，把 s 件拆成 01 背包）

比如 s=5，拆成 1,2,2 三个 “新物品”，就可以用 01 背包做，大幅提速

vector<pair<int,int>> goods;
for(int i=1;i<=n;i++)
{
    int v,w,s;
    cin>>v>>w>>s;
    int k=1;
    while(s>0)
    {
        int t=min(k,s);
        goods.emplace_back(t*v, t*w);
        s -= t;
        k *= 2;
    }
}
// 然后对goods跑01背包
for(auto &p : goods)
{
    int v=p.first, w=p.second;
    for(int j=m;j>=v;j--)
        dp[j]=max(dp[j],dp[j-v]+w);
}

进阶：单调队列优化多重背包（竞赛用）

---

4. 分组背包（每组里面最多选 1 个物品）

物品分成多组，每组若干物品，一组里最多挑一个

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 105;
int dp[M];

int main()
{
    int n, m;
    cin >> n >> m;
    // n组
    for(int i = 1; i <= n; i++)
    {
        int s; cin >> s; // 当前组物品数量
        // 背包容量倒序
        for(int j = m; j >= 0; j--)
        {
            for(int k = 1; k <= s; k++)
            {
                int v, w; cin >> v >> w;
                if(j >= v)
                    dp[j] = max(dp[j], dp[j - v] + w);
            }
        }
    }
    cout << dp[m];
    return 0;
}

顺序：先枚举组 → 倒序 j → 枚举组内物品