背包问题
2026-09-18 20:06:41
发布于：湖北
8阅读
0回复
0点赞
01背包
问题特点
- 每件物品只能选或不选（不能分割，不能重复选）。
- 目标：在不超过背包容量的前提下，使装入物品的总价值最大。
- 典型应用：资源分配、投资组合优化、任务调度等。
问题描述 - 背包容量 W（最大承重）。
- n 件物品，每件物品有：
- 重量 w[i]
- 价值 v[i]
求：选择哪些物品装入背包，使得总重量不超过 W，且总价值最大。
数据推导
| 容量 | 体积 | 价值 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 无物品 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 物品1 | 2 | 3 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 物品2 | 3 | 4 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 物品3 | 4 | 5 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
| 物品4 | 5 | 6 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10 |
状态转移方程
- 二维DP
dp[i][j]：前 i 件物品，背包容量 j 时的最大价值。
状态转移：
不选第 i 件物品：dp[i][j] = dp[i-1][j]
选第 i 件物品（如果 j ≥ w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
最终方程：
因为有二维dp数组，可以通过逆推得到最优解。if(dp[n][W]!=dp[n-1][W]) 就选择了物品n。
ll n,W;//物品数量和背包总容量
vector<ll> v,w,select;
void solve()
{
cin>>n>>W;
v.resize(n+1);
w.resize(n+1);
vector<vector<ll>> dp(n+1,vector<ll>(W+1,0));
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
for(int j=1;j<=W;j++){
if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[n][W]<<endl;
//逆推最优解：if(dp[n][W]!=dp[n-1][W]) 就选择了物品n。
while(W){
if(dp[n][W]!=dp[n-1][W]) {
select.push_back(n);
W-=w[n];
}
n--;
}
for(int i=0;i<select.size();i++) cout<<select[i]<<" ";
}
/*
in：
4 8
2 3
3 4
4 5
5 6
out:
10
4 2
*/
有帮助，赞一个