01背包问题
2026-01-16 20:33:27
发布于：广东
10阅读
0回复
0点赞
//01背包问题
//容量为k的背包,总共有n个物品,每个物品都有他的重量和价值
//每个物品可以选择或者不选且只能装下一个(01背包)
//在背包容量下能装入的物品最大价值是多少
//对于样例
// 10 4
// 2 1
// 3 3
// 4 5
// 7 9
//容量为10的情况下能够拿到的最大价值为12也就是拿2号物品和4号物品
//动态规划
//1.记忆化 存储想要的答案
//ans[i][j] //表示为第i个物品在容量为j的时候最大价值
//
//假设只拿物品2 1
//当前容量 0 1 2 3 4 5 6 7 8
//最大价值 0 0 1 1 1 1 1 1 1
//拿第二个物品3 3
//当前容量 0 1 2 3 4 5 6 7 8
//最大价值 0 0 1 3 3 4 4 4 4
//状态转移方程 --已知和未知的关系转化
//假设当前物品的重量为w,价值为v
//选择和不选择
//ans[i-1][j] --->不选择
//ans[i-1][j-w]+v --->选择
// ans[i][j] = max(ans[i-1][j],ans[i-1][j-w]+v);
//第一版:偏暴力方案时空复杂度为N*C
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
#define ll long long
int w[N],v[N];//重量和价值
int dp[N][N];//表示为第i个物品在容量为j的时候最大价值
void solve(){
int c,n;//c的容量,n个物品
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];//存储每个物品的重量和价值
}
for(int i=1;i<=n;i++){
for(int j=0;j<=c;j++){
dp[i][j]=dp[i-1][j];//对应不选的情况
if(j-w[i]>=0){//判断是否可以选择当前的物品,选择当前的物品i产生v[i]的价值
dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
}
cout<<dp[n][c];//选完最后一个物品,并且容量为c的情况即为答案
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
//第二版:优化方案时间复杂度:N*C,空间复杂度C
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
#define ll long long
int w[N],v[N];//重量和价值
int dp[N];//在容量为j的时候最大价值
void solve(){
int c,n;//c的容量,n个物品
cin>>c>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];//存储每个物品的重量和价值
}
for(int i=1;i<=n;i++){
for(int j=c;j>=0;j--){
if(j-w[i]>=0){//判断是否可以选择当前的物品,选择当前的物品i产生v[i]的价值
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
cout<<dp[c];//选完最后一个物品,并且容量为c的情况即为答案
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
这里空空如也
有帮助，赞一个