01背包-动态规划

最近在刷题的时候，碰到了01背包的问题，发现不是特别的熟悉。专门写的博客来强化下。

前提：

01背包-->对于某件物品来说只有两种可能，放入背包，还是不放。

假设现在有一个容量为C的背包，有N种物品，其中第 i 件物品的质量为 wi,价值为 vi。

我们设一个二维数组来存放对于第i价物品，背包容量分别为0...C时,.背包最大的价值。

       ---〉例如我们假设 m[i][j] 为在面对第i件物品时，背包容量为j时，背包的最大价值为m[i][j]的值

那我们如何确定 m[i][j] 的值呢？

先考虑一个问题：我们如果面对要不要把第i件物品放入背包时，会面临的情况。

       1）. 背包能否放下物品i

       2）.背包能放下，但要不要放。则需要考虑，把物品放入背包还是不放的哪个背包的最大价值更大即可。

因此我们可以得到递推式：

       m[i][j]: (1) j<w[i],放不下,则背包的最大价值为，m[i][j]=m[i-1][j]

                  (2) j>=w[i],放的下，要不要放

                              m[i][j] = max(m[i-1][j],m[i-1][j-w[i]]+v[i])   -->其中w[i]为第i件商品的重量，

                                                                                                       v[i] 为第i件商品的价值。

for(int i=1;i<=n;i++)
{
    for(int j=1;j<=m;j++)
    {
        if（j<w[i]）
        {
            m[i][j] = m[i-1][j];            
        }
        else
        {
            m[i][j] = max(m[i-1][j],m[i-1][j-w[i]+v[i]);
        }
    }
}

总结：其思想为分治，把问题规模缩小到可以很容易的求出，然后求解，最后合并。

               （所以很容易知道，采用递归也可以很容易的编写程序)

            当物品为0或者背包容量为0时，其最大价值为 0，然后就可以得到 物品为1是的背包的各种容量最大价值的情况，以此类推...便可知道