AKSZ-背包
2024-06-30 17:15:15
发布于：广东
10阅读
0回复
0点赞
dp-背包
题！
#include<bits/stdc++.h>
using namespace std;
//01背包，每个物品只能装或不装
int n,m,v[1005],w[1005],dp[1005][1005];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
dp[i][j]=max(dp[i-1][j],j>=v[i]?dp[i-1][j-v[i]]+w[i]:dp[i-1][j]);
}
}
cout<<dp[m][n];
return 0;
}
优化！
#include<bits/stdc++.h>
using namespace std;
//01背包，每个物品只能装或不装
int n,m,v[1005],w[1005],dp[2][1005],now=0,last=1;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=m;i++){
now^=1;last^=1;
for(int j=1;j<=n;j++){
dp[now][j]=max(dp[last][j],j>=v[i]?dp[last][j-v[i]]+w[i]:dp[last][j]);
}
}
cout<<dp[now][n];
return 0;
}
在优
#include<bits/stdc++.h>
using namespace std;
//01背包，每个物品只能装或不装
int n,m,v[1005],w[1005],dp[1005];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i]>>w[i];
}
for(int i=1;i<=m;i++){
for(int j=n;j>=v[i];j--){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[n];
return 0;
}
一个dp，一个滚动数组，一个压缩维度，9，因为6翻了
这里空空如也
有帮助，赞一个