朴素版:
//组合类DP->答案与选择的顺序无关.
#include<iostream>
using namespace std;
const int N=510,M=6010;
int f[M];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int v,w,s;
cin>>v>>w>>s;
for(int j=m;j>=v;j--)
for(int k=0;k<=s&&k*v<=j;++k)
f[j]=max(f[j],f[j-k*v]+k*w);
}
cout<<f[m]<<'\n';
return 0;
}
二进制优化版:
//组合类DP->答案与选择的顺序无关.
#include<iostream>
using namespace std;
const int N=510*10,M=6010;
int f[M],V[N],W[N];
int main()
{
int n,m,cnt=0;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int v,w,s;
cin>>v>>w>>s;
int k=1;
while(k<=s)
{
V[++cnt]=k*v;
W[cnt]=k*w;
s-=k;
k<<=1;
}
}
n=cnt;
for(int i=1;i<=n;++i)
for(int j=m;j>=V[i];j--)
f[j]=max(f[j],f[j-V[i]]+W[i]);
cout<<f[m]<<'\n';
return 0;
}
单调队列优化版:
//组合类DP->答案与选择的顺序无关.
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=6010;
int f[M],g[M],q[M];
int main()
{
int n,m,v,w,s;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>v>>w>>s;
memcpy(g,f,sizeof f);
for(int j=0;j<v;++j)//枚举模v意义下的余数.
{
int hh=0,tt=-1;
for(int k=j;k<=m;k+=v)
{
if(hh<=tt&&q[hh]<k-s*v) hh++;//把不在窗口里面的元素弹出.
while(hh<=tt&&g[q[tt]]-(q[tt]-j)/v*w<=g[k]-(k-j)/v*w) tt--;//判断相对大小前面的是否小于后面的,弹出冗余元素.
q[++tt]=k;//把当前元素的下标放进队列.
f[k]=g[q[hh]]+(k-q[hh])/v*w;//找到最大值,加上偏移量(队头元素相对于k有多少个v)
}
}
}
cout<<f[m]<<'\n';
return 0;
}