水贴！！！
2024-02-19 20:34:30
发布于：浙江
7阅读
0回复
0点赞
分组背包
#include<bits/stdc++.h>
using namespace std;
int n,V,t;
vector <int> w[1005];
vector <int> v[1005];
int dp[1005];
int main(){
cin>>V>>n>>t;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
w[z].push_back(x);
v[z].push_back(y);
}
for(int i=1;i<=t;i++){
for(int j=V;j>=0;j--){
for(int k=0;k<(int)w[i].size();k++){
if(j>=w[i][k]) dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
}
}
}
cout<<dp[V];
return 0;
}
NASA的食物计划
#include<bits/stdc++.h>
using namespace std;
int n,m,v[100005],w[100005],s[100005],dp[1005][1005],l;
int main(){
cin>>l>>m;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
}
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
for(int k=l;k>=v[i];k--){
dp[j][k]=max(dp[j][k],dp[j-w[i]][k-v[i]]+s[i]);
}
}
}
cout<<dp[m][l];
return 0;
}
猪猪存钱罐
#include<bits/stdc++.h>
using namespace std;
int n,k,m,c[1005],w[1005],dp[50005];
int main() {
cin>>k>>m;
cin>>n;
memset(dp,0x3f3f3f3f,sizeof dp);
m-=k;
for(int i=1; i<=n; i++) {
cin>>c[i]>>w[i];
}
dp[0]=0;
for(int j=1; j<=m; j++) {
for(int i=1; i<=n; i++) {
if(j>=w[i]) dp[j]=min(dp[j],dp[j-w[i]]+c[i]);
}
}
if(dp[m]>=0x3f3f3f3f) {
cout<<"This is impossible.";
}
else {
cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<".";
}
return 0;
}
潜水员
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int v[1005],c[1005],w[1005];
int dp[1005][1005];
int main() {
cin>>n>>m>>t;
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=t;i++){
cin>>v[i]>>c[i]>>w[i];
}
dp[0][0] = 0;
for(int i=1;i<=t;i++) {
for(int j=n;j>=0;j--) {
for(int k=m;k>=0;k--) {
dp[j][k]=min(dp[j][k],dp[max(j-v[i],0)][max(k-c[i],0)]+w[i]);
}
}
}
cout<<dp[n][m];
return 0;
}
这里空空如也
有帮助，赞一个