背包dp

2026/7/21 21:12:07

合集

是什么

顾名思义，就是有个背包，要拿来装东西，背包容量是有限的。你要决定要装什么东西进去 ~~（为什么是你）~~。

有三种背包：

01背包：每个物品只能选一次（也就是只有一个）。
完全背包：每个物品可以选无限次（也就是有无限个）。
多重背包：每个物品有数量上限，第 \(i\) 个物品最多选 \(c_i\) 次。

怎么实现

01背包

状态定义：\(dp_j\) 表示容量为 \(j\) 的背包能装的最大价值。

转移思路：对每个物品，决定“选”或“不选”。选的话从容量更小的状态转移过来。

关键点：容量循环必须从大到小（倒序），这样才能保证每个物品只被选一次。如果正着循环，同一个物品会被反复拿多次 ~~（别问我怎么知道的）~~。

example:
PID：P1048

思路：~~为什么要采药？~~ 这是一个01背包的板子题，~~water~~ 。题目写了每个草药只能采一次，不就是每个货物只能选一次吗？~~（我在反问什么）~~

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int w[3500],c[3500],dp[12883],n,m;
//我也不知道为什么dp我要开这样。
signed main(){cin>>m>>n;for(int i=1;i<=n;i++) cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--){//一定要倒序！！if(w[i]>j) dp[j]=dp[j];else dp[j]=max(dp[j-w[i]]+c[i],dp[j]);}}cout<<dp[m];return 0;
}

完全背包

状态定义：同上，dp[j] 表示容量为 j 的最大价值。

转移思路：每个物品可以拿无限次，所以容量循环从小到大（正序）。正着循环时，\(dp[j-w[i]]\) 可能已经考虑过当前物品了，相当于允许重复拿。

example:
PID：P1616

思路：~~为什么又是采药？~~ 这就是完全背包的板子了，每种草药可以采无限次，也就是每种物品有无限个了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int w[400000],c[400000],dp[10000000],m,n;
signed main(){cin>>m>>n;for(int i=1;i<=n;i++) cin>>w[i]>>c[i];for(int i=1;i<=n;i++){for(int j=w[i];j<=m;j++){if(w[i]>j) dp[j]=dp[j];else dp[j]=max(dp[j-w[i]]+c[i],dp[j]);}}cout<<dp[m];return 0;
}

完全背包

状态定义：同上。每个物品最多选 \(c_i\) 次。

最直接的做法：把每个物品拆成 \(c_i\) 个独立的“01 物品”，然后跑 01 背包。但这样复杂度太高（总物品数变成 \(sum(c_i)\)）~~小心炸~~。

优化手段：二进制拆分。把 \(c_i\) 拆成 \(1、2、4、8、...、剩余部分\)，每组打包成一个新的“物品”，重量 = 组内总重量，价值 = 组内总价值。这样 \(O(\log c_i)\) 个组就能表示 \(0\) 到 \(c_i\) 之间的任意选法，然后跑 01 背包。

example:
PID：T400036

思路：
每种物品能买 \(0\) 到 \(s\) 个。如果直接枚举买几个，复杂度 \(O(nsm)\)，这道题 \(s≤10\) 其实也能过，但标准做法才是重点。

二进制拆分：把 \(s\) 拆成 1、2、4、8、... 和剩下的零头。这样原来“选 \(0\) 到 \(s\) 个”的决策，等价于“从拆出来的 \(\log s\) 个新物品里做 01 背包选或不选”。

因为 \(1、2、4 \dots\) 这些数能组合出 0 到 s 之间的任意整数。

拆完之后，每个新物品有自己的重量（件数 × 单价）和价值（件数 × 单价值），然后对所有这些新物品跑一遍01背包。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w[10000000],c[10000000],s[10000000],dp[10000000];
signed main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i]>>c[i]>>s[i];for(int i=1;i<=n;i++){for(int k=1;s[i]>0;k<<=1){int x=min(k,s[i]);for(int j=m;j>=w[i]*x;j--)dp[j]=max(dp[j],dp[j-w[i]*x]+c[i]*x);s[i]-=x;}}cout<<dp[m];return 0;
}