742 B
742 B
完全背包求方案数二维降一维的推导过程
设第$i$个物品的体积:$v=w[i]$
二维递推式 $f[i][j] = f[i-1][j]+$$f[i-1][j-v]+f[i-1][j-2v]+...+f[i-1][j - (j/v) * v ]$ ①
尝试计算f[i][j-v]:
f[i][j-v]= f[i-1][j-v]+f[i-1][j-2v]+...+f[i-1][(j-v) - (j-v)/v * v ]
化简与等价变型
(j-v) - (j-v)/v * v = j-v -(j/v)*v+v= j - (j/ v)*v
$\therefore f[i][j-v]= $$f[i-1][j-v]+f[i-1][j-2v]+...+f[i-1][ j - (j/ v)*v]$ ②
将②代入①得：
f[i][j] = f[i-1][j]+f[i][j-v]
根据$01$背包优化的经验，我们知道从小到大去填充的话，就可以去掉第一维
得f[j]=f[j]+f[j-v]
即 f[j]+=f[j-w[i]]