背包问题

对于背包问题，我们需要使用动态规划的思想来解决问题。

例如一个问题， 选择n个物品重量w不超过n的最大价值v

首先是集合表示，可以表示为前 i 个物品 不超过 j 的重量的集合

集合的属性：最大/最小值

状态的计算: 对于[i，j] 我们需要对此进行一个集合的划分

一般来说，取最后一部进行划分：

以01 背包为栗：每个物品 选择和不选 ， 划分为2个集合 ，选择[i - 1, j - w[i] ]+ v[i], 不选择： [i - 1, j] , f[i, j] = max(f[i - 1, j], f[i - 1, j - v] + w)

完全背包： 每个物品，选0， 1个 ，2 个 ....... [i - 1, j], [i - 1, j - w[i] ]+ v[i]] , [i - 1, j - 2 w[i]] + 2 v[i] ...... ，优化：f(i, j) = max(f[i - 1, j ], f[i , j - v] + w )

for 物品
    for 体积 
        for 决策(选几个)

在 空间优化之后 : 2维优化1维，只有完全背包问题从小到大循环。