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.
23 lines
742 B
23 lines
742 B
### 完全背包求方案数二维降一维的推导过程
|
|
|
|
设第$i$个物品的体积:$v=w[i]$
|
|
|
|
二维递推式
|
|
$f[i][j] = f[i-1][j]+$<font color='red'>$f[i-1][j-v]+f[i-1][j-2v]+...+f[i-1][j - (j/v) * v ]$</font> ①
|
|
|
|
尝试计算$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]= $<font color='red'>$f[i-1][j-v]+f[i-1][j-2v]+...+f[i-1][ j - (j/ v)*v]$</font> ②
|
|
|
|
将②代入①得：
|
|
$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]]$ |