多重背包问题
结构体版
#include<iostream>
#include<vector>
using namespace std;
const int N=2010;
int f[N];
int n, m;
struct st{
int v, w;
};
vector<st> vecs;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
int v, w, s;
cin>>v>>w>>s;
for(int k=1; k<=s; k<<=1){
s-=k;
vecs.push_back({k*v, k*w});
}
if(s>0) vecs.push_back({s*v, s*w});
}
for(auto vec: vecs)
for(int j=m; j>=vec.v; j--)
f[j]=max(f[j], f[j-vec.v]+vec.w);
cout<<f[m]<<endl;
return 0;
}
pair版
#include<iostream>
#include<vector>
using namespace std;
const int M=2010;
int f[M];
int n,m;
vector<pair<int,int> >ve;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int k=1;k<=c;k*=2)
{
ve.push_back({k*a,k*b});
c-=k;
}
if(c>0)ve.push_back({c*a,c*b});
}
for(auto v:ve)
{
for(int j=m;j>=v.first;j--)
{
f[j]=max(f[j],f[j-v.first]+v.second);
}
}
cout<<f[m]<<endl;
return 0;
}