DP - Knapsack Summary

X. https://blog.csdn.net/u010982765/article/details/79044613
01背包问题内层循环必须是逆序的解释

有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

(01背包中这些物品每种都只有1个，每个物品只能装一次)

基本问题

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。

则其状态转移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }。可以压缩空间，f[v]=max{f[v],f[v-c[i]]+w[i]}

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：

“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。

如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，

那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，

此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i] 即f[i-1][v-c[i]]+w[i]。

为什么逆序

逆序的关键就在于这个状态转移方程

f[i][v]只与f[i-1][v]和f[i-1][v-C[i]]有关，即只和i-1时刻状态有关，所以我们只需要用一维数组f[]来保存i-1时的状态f[]。

假设i-1时刻的f[]为{a0，a1，a2，…，av}，那么i时刻的f[]中第v个应该为max(av,av-C[i]+W[i])即max(f[v],f[v-C[i]]+W[i])，

这就需要我们遍历V时逆序遍历，这样才能保证求i时刻f[v]时f[v-C[i]]是i-1时刻的值。如果正序遍历则当求f[v]时

其前面的f[0],f[1]，…，f[v-1]都已经改变过，里面存的都不是i-1时刻的值，这样求f[v]时利用f[v-C[i]]必定是错的值。最后f[V]即为最大价值。

数组遍历有时候必须逆序大多是这个原因

https://www.jiuzhang.com/qa/4313/

我没有想明白，为什么有重复的时候i是从coin开始算到s，而没有重复的时候i是从s开始算到coin？

/** 
 * @return number of ways to make sum s using repeated coins
 */
public static int coinrep(int[] coins, int s) {
    int[] dp = new int[s + 1]; 
    dp[0] = 1;          
    for (int coin : coins)      
        for (int i = coin; i <= s; i++)         
            dp[i] += dp[i - coin];                                  
    return dp[s];
}                                       
                                            
/**
 * @return number of ways to make sum s using non-repeated coins
 */
public static int coinnonrep(int[] coins, int s) {
    int[] dp = new int[s + 1];
    dp[0] = 1;  
    for (int coin : coins)
        for (int i = s; i >= coin; i--)
            dp[i] += dp[i - coin];              
    return dp[s];                                                   
}

无重复背包即01背包，得到的结果dp[i]是根据之前的结果来的，换句话说，是否选入当前物品是根据之前没有当前物品的子结果而做出的选择，是为了保证每一个物品的唯一性。
有重复背包即完全背包，每个物品都有无限的可重复性，所以当前的结果要从之前已经出现过当前物品的子结果中得到。
所以循环的方向要反一下，一个从下到上，一个从上到下。

X. 完全背包的顺序
https://blog.csdn.net/bujuan827/article/details/52176137
在这种情况下只能采用方式一，把对n的历遍放到第一层循环，这样才能避免把[1,5]、[5,1]算作两条路径。因为你限制了1,5的顺序，

到了i=5之后不可能在发生5,1的情况产生。

对于方式二，把对n的历遍放在第二层，对于任意的一个状态v,都可能历遍每一种硬币，会导致重复冗余的问题。

如果想加深理解，建议最好把两种方式都实现一下，单步执行查看
https://www.jiuzhang.com/qa/2863/

首先2维的状态是一个完整的状态，能表示状态详细的信息，为什么会有变成1维，实际上是在2维的前提下，优化了空间复杂度。
本质来说， f[i][*] 只和 f[i - 1][*] 有关，这给我了我们优化空间复杂度的契机，所有可以优化到一维。（又因为物品是取一个还是可以无限取，那么在一维状态的时候就要仔细考虑如何枚举状态的顺序）。

接下来是关于状态顺序的枚举。就是顺序是怎么思考的。
动态规划问题枚举的顺序只有一个原则：如果b状态的计算依赖于a状态，那么a状态必须在b状态之前被枚举和计算

k sum 问题也是如此。仔细看转移方程：
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
所以i需要从小到大枚举，j和t 也是如此。比如这里 你交换i和j的顺序，并没有剖坏我们的原则，则也是正确的，如下：

    public int  kSum(int A[], int k, int target) {
        int n = A.length;
        int[][][] f = new int[n + 1][k + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            f[i][0][0] = 1;
        }
        for (int j = 1; j <= k; j++) {
             for (int i = j; i <= n; i++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = 0;
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                } // for t
            } // for j
        } // for i
        return f[n][k][target];
    }

https://www.jiuzhang.com/qa/6568/

不同的顺序算一种方案，先for物品，再for容量，表示前i个物品用了容量j的价值。这样就没有考虑到顺序对答案的影响。
不同的顺序算多种方案，先for容量，再for物品，表示前j的容量，用了前i个物品的价值，这样就相当于当我用了j的容量，前面1->i-1的物品顺序已经确定了，方案数为dp[j]，那么再进行转移，这样就考虑了物品的顺序。

以后遇到这样的问题，要仔细分析一下状态的转移方程，哪些该转移，哪些不该转移，分析清楚了，做法自然就出来了。