二维费用背包和分组背包的英雄结合体
原题链接：94025.哈德莫得买挂
2025-12-11 15:16:35
发布于：河北
11阅读
0回复
0点赞
“二分”
#include<bits/stdc++.h>
#define maxn 1000
#define nullptr NULL
using namespace std;
int dp[maxn][maxn];
int hi[maxn];
int wi[maxn];
int ki[maxn];
int n,H,W;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>H>>W>>n;
for(int i=1;i<=n;i++)
{
cin>>hi[i]>>wi[i]>>ki[i];
for(int j=H;j>=hi[i];j--)
{
for(int k=W;k>=wi[i];k--)
{
dp[j][k]=max(dp[j][k],dp[j-hi[i]][k-wi[i]]+ki[i]);
}
}
}
cout<<dp[H][W];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int dp[1000000];
int g[10000][10000];
int n,v;
int w[100000],z[100000];
int b[100000];
int main(){
cin>>v>>n;
for(int i=1;i<=n;i++){
int x;
cin>>w[i]>>z[i]>>x;
g[x][++b[x]]=i;
}
for(int i=1;i<=n;i++){
for(int j=v;j>=0;j--){
for(int k=1;k<=b[i];k++){
if(j>=w[g[i][k]]){
dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);
}
}
}
}
cout<<dp[v];
return 0;
}
有帮助，赞一个