01背包问题wtf
背包问题f**k
2020-06-12
这几天做了几道题了，也陆陆续续看一些讲解，套路没问题，但是就是没法把背后所有细节理明白，这就不叫掌握，f**k. 分明是一个这么简单的问题。
01背包问题wtf
- 分明是随机放东西，怎么计算的时候按顺序来考虑。当前第i个物品不放，怎么变成来考虑 i-1之前物品的最优值？后面第i+k个物品放进去更优怎么考虑？
- dp[i][j]的时候，代表背包用前i个物品在重量为j的时候的最高价值，问题是如果前i个物品装不到j价值这么高怎么算？
- 前i个物品，需要按照规则排序吗，还是来一个算一个
- 0-1背包中的二维数组，压缩为一维数组，是怎么处理的
这个讲得很好，很容易就理解了。https://www.bilibili.com/video/BV1K4411X766
背包容量为0，或者物品为0，价值都为0
第1个物品体积为2，因此至少在dp[1][2]的位置才能放下一个，该物品的价值是3.
从第一个[1][2]的分析，直接就能推广到后面dp[1][x>=2]并设置所有值为3。
看这里的讲解，并没有认为dp[i][j]中必须已经凑够了j才行，而是在小于j的情况下的最大值？？？ 按照dp[i][j]是在dp[i][<j]中的最大值，则最后根本不需要扫描才对。但是记得其他地方看到的算法最后还是要扫一遍max(dp[n][0...v])才能得到最大值，这tmd不一样了，f**k!!!
背包的回溯，查看具体装了那些物品
回溯只要理解了思路就变得很容易。
如果当前w的物品没有被放进去，那么dp[i-1][j] = dp[i][j]，否则则是被放进去了。 如果放进去了，接下来要考虑的就是dp[i-1][j-w]和dp[i-2][j-w]之间的关系了。 这么一路往回推，只要表格还在，很容易就找出最后的路线。
代码
bilibili
https://www.bilibili.com/video/BV1qt411Z7nE?from=search&seid=14745193578293184439
这里面的写法，则是需要max(dp[n][0...j])才能得到最大值。
压缩成一维，细节还是没理清楚，估计得在问题里调试一遍我才能理解了。
完全背包问题，区别仅仅在于内层循环从小到大，还是没看懂，得做题仔细搞才懂了
重复背包问题，物品的数量并不是无限的
重复背包问题的二进制优化写法，太凶残了，主要为了减少遍历。一是把所有重复的变量扔进去，变成0-1背包问题，其次使用二进制组合得到所有的组合可能，减少了遍历次数。比如1，2，4的所有组合可能，只要使用7来表示即可。
二维背包，也就是背包有体积和重量的两重限制，求最大价值。转化成01背包的套路公式后，比较简单。
分组背包问题
百度
按照这里面百度百科的说法，也是要求在最后进行遍历选取最大一个。还是不理解为什么。
https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin
