背包问题 （knapsack）是一种组合优化的NPC问题（Nondeterministic Problem Complete- 千禧难题之一）

NP问题：非确定多项式，但能在多项式时间内找到解

什么时候用背包： 

什么时候用滚动数组： 

 dp[0][0 .... w] = 0, 表示0件物品装入背包最大价值为0

01 背包 01 knapsack：

N件物品，第i件重量为w[i]，价值为v[i]。在总重量不超过W，求最大价值。

        dp[i][j] = max(dp[i-1][j] (不选第i个背包）， dp[i-1][j-w[i]] + v[i] (选第i个背包））

dp[0,...,W] = 0
for i = 1,...,N:
    //必须逆向枚举，因为不能重叠
    for j = W,...,w[i]:
        dp[j] = max(dp[j], dp[j−w[i]]+v[i])

完全背包 unbounded knapsack： 

N件物品，第i件重量为w[i]，价值为v[i]。每种物品有无限个，在总重量不超过W，求最大价值

        1. dp[i][j] = max(dp[i-1][j] (不选第i个背包）， dp[i][j-w[i]] + v[i] (选第i个背包，装入后还可装））

        2.     假设 k  <= j/w[i]

                dp[i][j] = max{ dp[ i-1 ][ j - k*w[i] ] + k*v[i] }  for every k

dp[0,...,W] = 0
for i = 1,...,N：
    // 必须正向枚举，应为可以在已加过的背包中再加
    // dp(i, j-w[i])已经考虑过了 dp(i-1, j) 和 dp(i, j-2*w[i]) 
    for j = w[i],...,W：
        dp[j] = max(dp[j], dp[j−w[i]]+v[i])

多重背包 bounded knapsack：

N件物品，第i件重量为w[i]，价值为v[i]。每种物品有限个，在总重量不超过W，求最大价值

        1.      假设 k <= min( n[i], j/w[i] )

                 dp[i][j] = max{ dp[ i-1 ][ j - k*w[i] ] + k*v[i] } for every k

dp[0 ... n] = 0
for i=1 .... n:
    //必须逆向枚举，因为不能叠加（一维的时候）
    for j=W .... w[i]:
        // k 小于 min（有多少个物品i，当前背包容量能装多少个物品i）
        for k=0 ..... min(n[i], j/w[i])
            dp[j] = max(dp[j], dp[j - k*w[i]] + k*v[i])

背包衍生问题：

1. 装满问题：

        元素能否装满 j 容量的背包 （1 or 0）

        dp[i][j] = 1 or 0, 表示前i个元素能否装满成j

        dp[0][0] = 1， 前0个元素0和

                记住 j 要从0开始枚举，因为要更新

              dp[i][j] = dp[i-1][j] (不选）||   dp[i-1][j-nums[i]] (选）

        装满j容量的最大小值：

                 求最大，initialize 最小，反之亦然

                dp[i][j] = max or min (dp[i-1][j], dp[i-1][j-w[i]] + 1)  

-------------------------------------------------------------------------------------------------------------------------------

                                         习题练习

Partition Equal Subset Sum（分割等和子集）

给定一个只包含正整数的非空数组。问是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

                                                        01 背包 - 能否装满

Coin Change（零钱兑换）

给一个数量 k和硬币数组，求最少多少个硬币组成k, 每个硬币可以用无限个

                                                        完全背包 - 装满最小值