0-1背包问题中第二层循环为什么要倒序,完全背包问题中的第二层循环为什么又正序了

xiaoxiao2021-03-01  22

我们将一维数组看作是一条直线,并且用前面的元素值来更新后面的元素值,我们有两种选择,一是从前往后更新,二是从后往前更新,但这两种更新的效果完全不同:

从前往后更新,我们选择的是根据当前的状态值来更新本次的结果,从后往前更新,我们选择的是根据上一次的状态值来更新本次的结果。

0-1背包问题的状态转移方程是:f[i][j] = max(f[i-1][j], f[i-1][j - weight[i]] + value[i]);这个方程有如下特点:

1.f[i][j]的值只与上一行的值f[i-1][]有关

2.更新f[i][j]时,要用到上一行的旧值,

当用一维数组表示时,f[i] = max(f[i], f[i-weight[j]]+value[j]){注意:括号中的f[i]表示的是上一次的状态值},我们选择倒叙更新 

完全背包的状态转移方程是:f[i][j] = max(f[i-1][j], f[i][j - weight[i]] + value[i]);由于一个物品可以被选择多次,更新f[i][j]时,

f[i][j- weight[i]]可能因为放入物品i而发生变化。

用一维数组表示为:f[i] = max(f[i], f[i-weight[j]] + value[j]);选择正序更新。

 

转载请注明原文地址: https://www.6miu.com/read-4050111.html

最新回复(0)