二维写法时两种背包问题核心代码的区别:
可以看出,01背包用的是上一层的数据,完全背包用的是当前层的数据
所以优化为一维时,
01背包需逆序
for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
完全背包需正序
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
标签:背包,二维,01,一维,写法,逆序
From: https://www.cnblogs.com/LHgogo/p/16750201.html