01背包问题

服了，背包问题我真的是学了就忘学了就忘学了就忘……

写个博客总结一下，加深加深印象（供以后忘了的时候参考）。

问题描述：

有N件物品和一个容量为V的背包。第i件物品的体积是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

问题特点：

每种物品只有一件，有两个状态，选择放或者不放。

状态转移方程：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])。

dp[i][j]表示装到第i个物品时背包的最大价值，dp[i-1][j]可以理解为我们不装i物品，此时背包中的最大价值就是装到第i-1个物品时背包的最大价值；dp[i-1][j-w[i]]+v[i]可以理解为我们装了i物品，既然装了i物品，那就应该从总容量中减去第i个物品的体积w[i]，此时背包剩余容量为j-w[i]，背包最大价值也要加上i物品的价值。

 二维数组：

for(int i=1;i<=N;i++)
{
    for(int j=0;j<=V;j++)
    {
        if(j//第i件物品太重，放不进去
            dp[i][j]=dp[i-1][j];
        else
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    }
}

对于上面的状态转移方程我们无法再进行时间优化，但可以进行空间优化。

可以发现这样的问题：

①二维数组的遍历顺序为从第一行开始一行一行遍历，且遍历到第i行时不会用到第i-2行的数据，那么i-2行及以前的数据都i没有用了，我们可以将其清除。

②遍历每一行时候只用到当前容量j和j-w[i]的数据，也就是第 i 次遍历只需要 第 i-1 次遍历中容量小于等于 j 的数据。

所以我们可以将利用滚动数组优化空间。

一维数组：

for(int i=1;i<=N;i++)
{
    for(int j=V;j>=0;j++)
    {
        if(j//第i件物品太重，放不进去
            dp[j]=dp[j];
        else
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

j从背包容量为V开始遍历，这样可以保证dp[i][j]和dp[i][j-w[i]]中保存的都是第i-1行的数据。

有个问题：j只需要遍历到j>=w[i]。即：

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

 例题 l