学步园

        01背包是最最基础的背包，它的问题特征是给定n物品，每种物品一个， 体积为c，价值为w，现在给定空间V，问在V的空间下，如何放置使得价值尽量大

        我们很快可以列出方程1  dp[i][j] = max{ dp[i - 1][j], dp[i - 1][j - c[i]] + w[i] }

        当然我写这篇随笔的目的不是为了说明这个方程，一般我们对于01背包的题，都可以用一个一维数组来搞定，先看方程2

        dp[j] = max{dp[j], dp[j - c[i]] + w[i] }

       这里的 dp[j] 相当于 状态 dp[i][v]

       值得注意的是

for (int i = 1; i <= n; i++)
{
    for (int j  = v; j >= 0; j--)
    {
        dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    }
}

      对于体积的循环必须是逆序，why？

      首先，由方程1知道，决策第i件物品时，只和前 i- 1件物品有关;

     试想下，加入把体积的循环改成顺序，由于 j - c[i]  < j,则由第i - 1个状态的出来的dp[j - c[i] ]这个状态就会被第i个状态覆盖掉;

    换句话说，如果顺序循环，那么dp[i][j] 将会由 dp[i][j - c[i] ] 得到，显然和方程1矛盾了，所以只有逆序循环才能满足dp[i][j] 由 dp[i][j - c[i] ]推到

     (因为此时处理dp[j]时，dp[j - c[i]] 还没有被覆盖，所以是正确的).