求最大值最小值初始化总结
二维情况
1、体积至多j
f[i,k] = 0,0 <= i <= n, 0 <= k <= m(只会求价值的最大值
循环从[j,V]
2、体积恰好j,
当求价值的最小值:f[0][0] = 0, 其余是INF
当求价值的最大值:f[0][0] = 0, 其余是-INF
循环从[j,V]
3、体积至少j
f[0][0] = 0,其余是INF(只会求价值的最小值)
循环从[0,V]
1与2初始化不同的原因:
对于1:f(0,v)表示前0个物品 体积不超过v,重量为0
对于2/3:f(0,v)表示前0个物品 体积不小于/恰好等于v,该情况不合法
求最小值,inf = float(“inf”)
求最大值,inf = -float(“inf”),如果没负数,可以用0初始化
当运用到inf,需要考虑边界问题:
边界是inf,不会被max/min更新进去,相当于“-1”,于是需要对首项初始化,以支持后面的更新