问题描述:
有 $N$ 种物品(属性为价值和体积)和容量为 $V$ 的背包,每种物品可以选多次,选出装入总价值最大的物品集合
题解:
求解:f[i,j]=f[i-1,j-v[i]*k]+w[i]*k
f[i,j]=Max(f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w...)
f[i,j-v]=Max( f[i-1,j-v] , f[i-1,j-2v]+w , f[i-1,j-3v]+2w...)
即:f[i,j]=Max(f[i,j] , f[i,j-v]+w)
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
//1.三维
for(int k=0;k*v[i]<=j;k++)
f[i][j]=max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
//2.优化为二维
if(j<v[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
一维数组方案: f[j]=max(f[j],f[j-v[i]]+w[i]);
$j$ 正序,因为可以选多次,无需在意上一轮状态