01背包
2026-01-03 11:59:43
发布于：四川
4阅读
0回复
0点赞
//01背包
定义：有一个容量为V的背包和n个物品，每个物品有一个体积vi和一个价值wi。
要求选择若干物品装入背包，使得装入背包中物品的总价值最大。
其中每个物品只能选择一次。
/*二维*/
状态转移方程：
对于第i个物品，有两种选择：
1.不放入背包，此时背包的最大价值为f(i-1,j);
2.放入背包，此时背包的最大价值为f(i-1,j-vi)+wi;
所以状态转移方程为：f(i,j) = max(f(i-1,j),f(i-1,j-vi)+wi);
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN];//物品体积
int w[MAXN];//物品价值
int f[MAXN][MAXN]; //最大价值
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=1;j<=m;j++){
//装不下第i个物品，最大价值为前i-1个物品的最大价值
f[i][j]=f[i-1][j];
//能够装下第i个物品，判断是否选择第i个物品
if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
}
}
cout << f[n][m] << endl; //输出最大价值
return 0;
}
/*一维*/
状态转移方程：
对于第i个物品，有两种选择：
1.不放入背包，此时背包的最大价值为f(j);
2.放入背包，此时背包的最大价值为f(j-vi)+wi;
所以状态转移方程为：f(j) = max(f(j),f(j-vi)+wi);
代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int v[MAXN];//物品体积
int w[MAXN];//物品价值
int f[MAXN];//最大价值
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=m; j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout << f[m] << endl;//输出
return 0;
}
这里空空如也
有帮助，赞一个