白话背包之全然背包

借着前面的  白话背包之01背包 的基础，来结合图看看全然背包是个什么东东，希望以后自己看能一目了然，能对刚接触的童鞋有帮助是最好只是滴

一：关于全然背包

有N个物品，每一个物品（有无限多个） i 相应有重量w[i]、价值va[i]。有一个背包能够放M重的物品，如今让你从N钟物品中选择一些物品，在不超过背包上限情况使得背包装的价值最大。

二：初步了解全然背包算法

那么这里看看状态转移方程：

dp[i][j]=max{dp[i-1][j-k*w[i]]+k*va[i] | 0<=k*va[i]<=M}，理解为在考虑第i件物品的时候，背包剩余容量为j下获得的最大利益。

看看代码：解释清楚再优化

for(int i = 1; i <= N; i ++){
    for(int j = w[i]; j <= M; j ++){
        int Max = 0;
        for(int k = 0; k*w[i] <= M; k ++){
            Max = max(Max,dp[i-1][j-k*w[i]]+k*va[i]);
        }
        dp[i][j] = Max;
    }
}

那么先考虑 dp[1][3]的情况，我们发现，在这里，k循环的时候仅仅能取 1，使得dp[1][3] = dp[0][3-1*3]+1*2 = dp[0][0]+2 = 2;意思是，考虑第一件物品，背包大小为3的情况，我们能放1个第一件物品(多了就放不下啦)，使得这个状态下收益最大。

那么同理，考虑第一件物品的时候，背包的其它状态更新例如以下：

能够发现，一直到背包容量为6之前，都仅仅能够放下一个第一件物品，那么容量为6的时候，刚好就能够放进两个

那么这里我们就能够发现，事实上第一件物品、容量为6的状态dp[1][6]，能够在dp[1][3]的状态得到，而且其它的状态也类似。。。

三：那么我们能够引入优化的一维数组，同一时候也减少时间复杂度

先看看一维数组的算法：

for(int i = 1; i <= N; i ++){
    for(int j = w[i]; j <= M; j ++){
        dp[j] = max(dp[j],dp[j-w[i]]+va[i]);
    }
}

上面说其它状态类似，究竟怎么类似的呢?，看图：

那么，到6之前就变成了

那么更新 dp[6]的时候，就能够依靠dp[3]+va[1] 得到，那么在考虑其它的物品的时候，也就类似啦。那么这里也就是须要差别01背包的地方。。。就是for循环的时候，是从小到大，由于考虑当前状态dp[j]的时候，我们是必须依靠前面已有的状态 (也就是，前面一定放了这件物品，我们再放一件，看能不能得到更大利益) 来更新如今的状态。

OK，到此全然背包完成

个人愚昧观点，欢迎指正与讨论