9.背包问题
原题链接：125757.9.背包问题
2026-06-27 16:08:33
发布于：上海
4阅读
0回复
0点赞
01背包：
#include<bits/stdc++.h>
using namespace std;
int f[35][205],w[35],v[35],c,n;
int main(){
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=1;j<=c;j++){
if(j<w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
}
}
cout<<f[n][c];
return 0;
}
01背包(优化)：
#include<bits/stdc++.h>
using namespace std;
int f[30005],w[30005],v[30005],c,n;
int main(){
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--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
cout<<f[c];
return 0;
}
完全背包：
#include<bits/stdc++.h>
using namespace std;
int w[50],v[35],f[50][1010];
int main(){
int t,n;
cin>>t>>n;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=t;j++){
if(j<w[i]) f[i][j]=f[i-1][j];
else f[i][j]=max(f[i][j-w[i]]+v[i],f[i-1][j]);
}
}
cout<<f[n][t];
return 0;
}
多重背包：
#include<bits/stdc++.h>
using namespace std;
int n,c,w[90010],v[90010],f[305];
int main(){
cin>>c>>n;
int cnt=0;
for(int i=1;i<=n;i++){
int ww,vv,ss;
cin>>ww>>vv>>ss;
for(int j=1;j<=ss;j++){
cnt++;
w[cnt]=ww;
v[cnt]=vv;
}
}
for(int i=1;i<=cnt;i++){
for(int j=c;j>=w[i];j--){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
cout<<f[c];
return 0;
}
分组背包：
#include<bits/stdc++.h>
using namespace std;
struct node{
int w,c;
};
vector<node> ve[20];
int v,n,t;
int dp[19][2009];
int main(){
cin>>v>>n>>t;
int w,c,p;
for(int i=1;i<=n;i++){
cin>>w>>c>>p;
ve[p].push_back((node){w,c});
}
for(int i=1;i<=t;i++){
for(int j=0;j<=v;j++){
dp[i][j]=dp[i-1][j];
for(int k=0;k<ve[i].size();k++){
if(j>=ve[i][k].w){
dp[i][j]=max(dp[i][j],dp[i-1][j-ve[i][k].w]+ve[i][k].c);
}
}
}
}
cout<<dp[t][v];
return 0;
}
这里空空如也
有帮助，赞一个