完全背包问题

f[i][j]

f[i][j]表示从1到i个物品中选,质量不超过j的选法

子集的划分

对第i个物品选的个数进行划分,是选0个,1个,2个,···,还是k个,···到不能选为止

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w ,  f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max(            f[i-1,j-v]   ,  f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系： 
                        f[i][j]=max(f[i,j-v]+w , f[i-1][j]) 

完全背包问题和0-1背包问题状态转移方程的区别

f[i][j] = max(f[i - 1][j],    f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i - 1][j],f [i] [j-v[i]]+w[i]);//完全背包问题

完全背包问题的遍历顺序

for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            //因为完全背包问题每个物品可以选无数次
            //所以不需要从后向前遍历

求组合数和求排列数的for循环嵌套问题

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

for (int i = 0; i < coins.size(); i++) 
{ // 遍历物品
    for (int j = coins[i]; j <= amount; j++) 
    { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}
//假设：coins[0] = 1，coins[1] = 5。
//那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有
//{1, 5}这种情况。而不会出现{5, 1}的情况。
//所以这种遍历顺序中dp[j]里计算的是组合数！

for (int j = 0; j <= amount; j++) 
{ // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) {
    // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}
//背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
//此时dp[j]里算出来的就是排列数！