You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
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]]