背包问题------ 分类： ACM 2015-08-03 20:57 1人阅读 评论(0

对于背包问题，网上有很多博客= =，如果有不小心点进来的朋友，看到我挫逼的博文然后看不懂，可以自行百度一篇，其中本文的博文内
容参照 http://blog.csdn.net/lyhvoyage/article/details/8545852#0-qzone-1-46291-d020d2d2a4e8d1a374a433f596ad1440
那里讲的很详细
01背包问题
01背包问题的模型可以总结为在N件物品，体积为Vi，价值为Wi，然后有一个体积为V的背包，然后求背包最多能装多大价值的的物品

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

完全背包
然后让我们把问题扩展一下，若物体不止拿一次，可以拿若干干次，那这个问题就变成完全背包问题
代码其实和上面那个很像

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

多重背包“
然后让我们作死再把问题变一下，物品的数量有限制= =然后怎么办捏，这个时候二进制就发挥它强大的功能，比如7的二进制是111，它可以分解为001,010,100这三个数可以组成任何小于等于7的数，而且不同的组合可以得到不同的数，所以根据这个原理，我们可以把这个问题转化为01背包问题，其实就是把多个物品用二进制分解为每一种物品都只有一个= =

x代表物体的体积，y代表价值，z代表物体的个数
    scanf("%d %d %d",&x,&y,&z);
        for(int k=1;k<=z;k<<=1)
        {
            w[count]=x*k;
            v[count++]=y*k;  
            z=z-k;
        }
        if(z>0)//这步其实很容易遗漏
        {
            w[count]=z*x;
            v[count++]=z*y;
        }

搞完那个二进制就可以直接用01背包来做啦

    for(int i=0;i<count;i++)
    {
        for(int j=W;j>=w[i];j--)
        {
            f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    }