提出观点:f[0][0]=0,其余状态全初始成正无穷,这种初始化方式是,f[i][j] 代表恰好氧气为i,氮气为j的初始方式
例如我们做货币系统和数字组合那种题的时候,就是这种初始化方式
不理解为什么是这种初始化方式和 至多做法与恰好做法的区别的可以看这一部分(懂得可以跳过)
我们最开始接触的最基础的01背包问题
初始化f数组全为0 那么用第一个物品去更新状态的时候
这里为了方便讲述
举个数字实例
背包总容积是100 第一个物品 体积为5 价值为10
那么用第一个物品更新完f数组
不仅是f[5]=10 还会有f[6]=10 f[7]=10 f[8]=10 ........
对应的这些更新状态的由来分别是
f[0]=0 f[1]=0 f[2]=0 f[3]=0 ........
如果我们换一个初始化方式
只有f[0]=0 其余均为负无穷(目的是与题目dp的属性相反)
那么会得到
f[5]=10 f[6]=-INF f[7]=-INF f[8]=-INF
所以说黑体字的初始化方式是恰好做法的初始化方式
下面谈一谈恰好做法于本题中实际应用
只不过在后续的用物品更新状态的时候,除了一般的更新,还进行了增加物品的操作
这里增加物品的操作指的是
比如说题目中有个原物品
5 4 10
提供氧气5 提供氮气 4 耗费10 的重量
我们除了用5 4 10去更新状态
我们还会用
5 3 10 5 2 10 5 1 10 5 0 10
4 3 10 4 2 10 4 1 10 4 0 10
3 3 10 3 2 10 3 1 10 3 0 10
2 3 10 2 2 10 2 1 10 2 0 10
的这些物品去更新状态
用题中的原物品和原物品的同等花费的一部分 去进行”恰好“做法 ,得到的f[n][m] 即为至少氧气为n 氮气为m的最小花费
总结: 用原物品与原物品的部分 去进行恰好做法 就是 至少 做法
我好想也是这么想的,请问为什么tle了呢?
写错了, 改为负无穷后, f[5] = 10, 你写的 f[5] = 0
已改正
代码部分可以参考y总的代码,本题主要说思路及理解
或者是 看完本篇能更好的去理解y总讲的 ’‘至少‘’ 做法