01背包详解
2026-01-11 17:53:56
发布于：广东
13阅读
0回复
0点赞
/*
//10的容量,4的物品数量,求满足容量的情况下最大价值
//重量,价值
2 2
3 3
4 8
7 9
1.记忆化 记忆所需要的答案
ans[i] i容量的情况下最大价值
ans[0] 0
ans[1] 0
ans[2] 2
ans[3] 3
ans[4] 8
ans[5] 8
ans[6] 10
ans[7] 11
ans[8] 11
ans[9] 13
ans[10] 13
ans[i][j],拿第i个物品,容量为j时候的最大价值
2.状态转移方程
w[N],v[N]//重量,价值
拿,不拿(选最大)
ans[i][j]=max(ans[i-1][j],ans[i-1][j-w[i]]+v[i]);
不拿: ans[i-1][j]
拿了: ans[i-1][j-w[i]]+v[i];
*/
/*
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define ll long long
int c,n;//总共c的容量,n的物品
int w[N],v[N];//重量,价值
int ans[N][N];
//时间复杂度c*n
//空间复杂度c*n;
void solve(){
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++){
ans[i][j]=ans[i-1][j];
if(j-w[i]>=0){
ans[i][j]=max(ans[i][j],ans[i-1][j-w[i]]+v[i]);
}
}
cout<<ans[n][c]<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define ll long long
int c,n;//总共c的容量,n的物品
int w[N],v[N];//重量,价值
int ans[N];//存储容量为i时候最佳的价值
//时间复杂度c*n
//空间复杂度max(c,n);
void solve(){
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>=w[i];j--){
ans[j]=max(ans[j],ans[j-w[i]]+v[i]);
}
cout<<ans[c]<<endl;
}
int main(){
int t=1;
// cin>>t;
while(t--){
solve();
}
}
有帮助，赞一个