多重背包

妖狐艹你老母 2022-05-31 01:19 223阅读 0赞

**问题：**

一个容量为c的背包，还有一些物品（每个物品有具体的数量num），这些物品的体积w和价值v各不相同。求出能在不超过c的情况下尽可能的使价值最大。

对于多重背包问题，可以根据每个物品的数量分解成两种情况：  
1.当num >= c / w时，相当于物品可以无限使用，即转化为完全背包求解。

2.当num< c / w时， 可转化为放物品的数量为1、2、3……c个，即转化为01背包求解。

其中0-1背包的地方可以使用二进制拆分：7的二进制 7 = 111 它可以分解成 001 010 100 这三个数，可以组合成任意小于等于7 的数，而且每种组合都会得到不同的数。15 = 1111 可分解成 0001  0010  0100  1000 四个数字  如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成 7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13  的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种思想去把多件物品转换为多种一件物品，就可用01 背包求解了。

不多说上代码（模板）：

#include<stack>
    #include<queue>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    int dp[10101];
    int num[1010];
    int w[1010];
    int v[1010];
    int n,c;
    void beibao1(int w,int v)
    {
        for(int i=c; i>=w; i--)
        {
            dp[i]=max(dp[i],dp[i-w]+v);
        }
    }
    void beibao2(int w,int v)
    {
        for(int i=w; i<=c; i++)
            dp[i]=max(dp[i],dp[i-w]+v);
    }
    int wanquanbeibao(int n,int c,int num[],int w[],int v[])
    {
        int i,j;
        memset(dp,0,sizeof(dp));
        for(i=1; i<=n; i++)
        {
            if(num[i]*w[i]>c)//当超出背包空间时,相当于物品可以无限使用，变成完全背包
                beibao2(w[i],v[i]);
            else//当没有超出可转化为放物品的数量有限，则为01背包
            {
                int k=1;
                while(k<num[i])
                {
                    beibao1(k*w[i],k*v[i]);
                    num[i]-=k;
                    k*=2;//二进制拆分
                }
                beibao1(num[i]*w[i],num[i]*v[i]);
            }
        }
        return dp[c];
    }
    int main()
    {
        while(scanf("%d%d",&n,&c)!=EOF)
        {
            int i,j;
            for(i=1; i<=n; i++)
                scanf("%d",&num[i]);
            for(i=1; i<=n; i++)
                scanf("%d",&w[i]);
            for(i=1; i<=n; i++)
                scanf("%d",&v[i]);
            printf("%d\n",wanquanbeibao(n,c,num,w,v));
        }
        return 0;
    }

例题： [点击打开链接][Link 1]航电的一道例题，只需把上面改一下就可以了

改动代码：

#include<stack>
    #include<queue>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<algorithm>
    using namespace std;
    int dp[10101];
    int num[1010];
    int w[1010];
    int v[1010];
    int n,c;
    void beibao1(int w,int v)
    {
        for(int i=c; i>=w; i--)
        {
            dp[i]=max(dp[i],dp[i-w]+v);
        }
    }
    void beibao2(int w,int v)
    {
        for(int i=w; i<=c; i++)
            dp[i]=max(dp[i],dp[i-w]+v);
    }
    int wanquanbeibao(int n,int c,int num[],int w[],int v[])
    {
        int i,j;
        memset(dp,0,sizeof(dp));
        for(i=1; i<=n; i++)
        {
            if(num[i]*w[i]>c)//当超出背包空间时,相当于物品可以无限使用，变成完全背包
                beibao2(w[i],v[i]);
            else//当没有超出可转化为放物品的数量有限，则为01背包
            {
                int k=1;
                while(k<num[i])
                {
                    beibao1(k*w[i],k*v[i]);
                    num[i]-=k;
                    k*=2;//二进制拆分
                }
                beibao1(num[i]*w[i],num[i]*v[i]);
            }
        }
        return dp[c];
    }
    int main()
    {
        int test;
        scanf("%d",&test);
        while(test--)
        {
            int i,j;
            scanf("%d%d",&c,&n);
            for(i=1; i<=n; i++)
                scanf("%d%d%d",&w[i],&v[i],&num[i]);
            printf("%d\n",wanquanbeibao(n,c,num,w,v));
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2191http://