由于每件物品有k个随便选。所以状态转义方程如下:
设f[i][j]为选完第i类物品后,背包容量为j的最大价值。
for (int i = 1;i<=n;i++){ //一共i类物品
for (int j = 0; j <=m; j++){ //背包大小为m
for (int k = 0; k * v[i] <= j; k++){ //背包能装下的话一个一个k往里放
f[i][j]=max(f[i-1][j - k*v[i]]+k*w[i],f[i][j]); //不停的更新f[i][j]方案,直到装不下就是当前最优. k=0即i物品一个不选
}
}
}
不难发现k重循环可省略,一个一个往里放。(应该没错吧?) reference
动态规划的优化一般都是对代码或者状态计算方程进行一个等价变形。在考虑动态规划问题的时候,一定要先把基本的形式写出来,然后再对它进行优化。(这部分参考了@Tell_me的题解)
for (int i = 1; i <= n; i ++ ){
for (int j = 0; j <= m; j ++ ){
if (v[i] <= j){f[i][j]= max(f[i][j-v[i]]+w[i],f[i-1][j]);}
else {f[i][j]=f[i - 1][j];}
}
}
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式,可得出如下递推关系:
f[i][j]=max(f[i,j-v]+w , f[i][j])
for (int i = 1;i<=n;i++){ //一共i类物品
for (int j = v[i]; j <=m; j++){ //背包大小为m
f[j]=max(f[j-v[i]+w[i],f[j]);
}
}
cout << f[m] << endl;