2024.9.21 计划

项目部分

偷懒一天

个人学习部分

昨天DP的两个题
DP一个题
1.多重背包问题 III

总结

01背包的优化：由于一般状态转移方程是:
f[i][j]= f[i - 1][j] + f[i - 1][j - v]
所以说优化空间的时候要倒着枚举体积，否则会导致f[i - 1][j - v]被更新成f[i][j - v]

完全背包的优化：一般状态转移方程是:
f[i][j] = f[i - 1][j] + f[i - 1][j - v] + f[i - 1][j - v * 2] + ... + f[i - 1][j - v * k]
考虑到f[i][j - v] = f[i - 1][j - v] + f[i - 1][j - v * 2] + ... + f[i - 1][j - v * k]
所以可以得到优化：f[i][j] = f[i - 1][j] + f[i][j - v]
由于这里用到的是同一层的状态，所以要正着枚举体积，让前面的状态先算出来。

搞清楚了极大线性无关组的求法，\(O(nm)\)的时间用完全背包就可以做出来。
没精力去搞多重背包了，要先复习一下单调队列。