动态规划 0-1背包备忘

我也是经常忘= =。。写个备忘
有n件物品和一个容量为V的背包，第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。
每种物品只有一件，可以选择放或者不放。
dp[i][j]表示前i件物品，j表示可以容纳的重量
dp[i][j] = max(dp[i - 1][j] ，dp[i][ j - w[i]] + v[i])

for i in 1..<n{
            
            for j in 0...W{
                
                if j<w[i] {
                    
                    dp[i][j] = dp[i - 1][j]
                    
                }else{
                    
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])
                
                }

 
            }
  
        }

二维转一维

for i in 1..<n{
            
            for j in stride(from: W, through: w[i], by: -1){
                    dp[j] = max(dp[j], dp[j - w[i]] + v[i])                
                }
            }
}

初始化
如果是恰好装满背包。。
那么dp[0] = 0 其他均为 负无穷大
如果不要求恰好装满背包，而是要求价值最大
那么需要初始化的时候将dp[0...n]全部初始化为0

为什么呢？可以这样理解：初始化的dp数组事实上就是在没有任何物品可以放入背包时的合法状态。
如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。
如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。