背包问题 订阅
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。 展开全文
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkle和Hellman提出的。背包问题已经研究了一个多世纪,早期的作品可追溯到1897年 [1]  数学家托比亚斯·丹齐格(Tobias Dantzig,1884-1956)的早期作品 [2]  ,并指的是包装你最有价值或有用的物品而不会超载你的行李的常见问题。
信息
外文名
Knapsack Problem
提出者
Merkle-Hellman
中文名
背包问题
应用领域
运筹学,应用数学,密码学等
背包问题应用
1998年的石溪布鲁克大学算法库的研究表明,在75个算法问题中,背包问题是第18个最受欢迎,第4个最需要解决的问题(前三为后kd树,后缀树和bin包装问题)。 [3]  背包问题出现在各种领域的现实世界的决策过程中,例如寻找最少浪费的方式来削减原材料, [4]  选择投资和投资组合, [5]  选择资产支持资产证券化 [6]  ,和生成密钥为Merkle-Hellman [7]  和其他背包密码系统。背包算法的一个早期应用是在测试的构建和评分中,测试者可以选择他们回答哪些问题。对于小例子来说,这是一个相当简单的过程,为测试者提供这样的选择。例如,如果考试包含12个问题,每个问题的价值为10分,测试者只需回答10个问题即可获得100分的最高分。然而,在点值的异质分布的测试 - 即不同的问题值得不同的点值 - 更难以提供选择。 Feuerman和Weiss提出了一个系统,其中学生被给予一个异质测试,共有125个可能的点。学生被要求尽可能回答所有的问题。在总点数加起来为100的问题的可能子集中,背包算法将确定哪个子集给每个学生最高的可能得分。 [8] 
收起全文
精华内容
参与话题
问答
  • 经典背包问题 01背包+完全背包+多重背包

    万次阅读 多人点赞 2013-04-06 20:27:01
    01 背包 有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。  int f[w+1]; //f[x] 表示背包容量为x 时的最大价值  for (int i=0; i  ...

    01 背包

    有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。  

    int f[w+1];   //f[x] 表示背包容量为x 时的最大价值
    for (int i=0; i<n; i++)
        for (int j=w; j>=size[i]; j--)
            f[j] = max(f[j], f[j-size[i]]+value[i]);
    



    完全背包 

    如果物品不计件数,就是每个物品不只一件的话,稍微改下即可  

    for (int i=0; i<n; i++)
        for (int j=size[i]; j<=w; j++)
            f[j] = max(f[j], f[j-size[i]]+value[i]);
    

      
            f[w] 即为所求  
            初始化分两种情况:
            1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;  

            2、如果不需要正好装满 f[0~v] = 0;  

            举例:

    01背包

    V=10,N=3,c[]={3,4,5}, w={4,5,6}

    (1)背包不一定装满

          计算顺序是:从右往左,自上而下:因为每个物品只能放一次,前面的体积小的会影响体积大的

    (2)背包刚好装满    

          计算顺序是:从右往左,自上而下。注意初始值,其中-inf表示负无穷

    完全背包

    V=10,N=3,c[]={3,4,5}, w={4,5,6}

    (1)背包不一定装满

    计算顺序是:从左往右,自上而下:  每个物品可以放多次,前面的会影响后面的

    (2)背包刚好装满

    计算顺序是:从左往右,自上而下。注意初始值,其中-inf表示负无穷

    多重背包:  
             多重背包问题要求很简单,就是每件物品给出确定的件数,求可得到的最大价值  
             多重背包转换成 01 背包问题就是多了个初始化,把它的件数C 用二进制分解成若干个件数的集合,这里面数字可以组合成任意小于等于C的件数,而且不会重复,之所以叫二进制分解,是因为这样分解可以用数字的二进制形式来解释  
           比如:7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数,而且每种组合都会得到不同的数  
           15 = 1111 可分解成 0001  0010  0100  1000 四个数字  
            如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成  7以内任意一个数,即1、2、4可以组合为1——7内所有的数,加上 0110 = 6 可以组合成任意一个大于6 小于等于13的数,比如12,可以让前面贡献6且后面也贡献6就行了。虽然有重复但总是能把 13 以内所有的数都考虑到了,基于这种思想去把多件物品转换为,多种一件物品,就可用01 背包求解了。  
           看代码:  
          
    int n;  //输入有多少种物品
    int c;  //每种物品有多少件
    int v;  //每种物品的价值
    int s;  //每种物品的尺寸
    int count = 0; //分解后可得到多少种物品
    int value[MAX]; //用来保存分解后的物品价值
    int size[MAX];  //用来保存分解后物品体积
    
    scanf("%d", &n);    //先输入有多少种物品,接下来对每种物品进行分解
    
    while (n--)     //接下来输入n中这个物品
    {
        scanf("%d%d%d", &c, &s, &v);  //输入每种物品的数目和价值
        for (int k=1; k<=c; k<<=1)   //<<右移 相当于乘二
        {
            value[count] = k*v;
            size[count++] = k*s;
            c -= k;
        }
        if (c > 0)
        {
            value[count] = c*v;
            size[count++] = c*s;
        }
    }


    定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

    证明如下:

    (1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

    (2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

    (3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

    (证毕!)


          

            现在用count 代替 n 就和01 背包问题完全一样了  

    杭电2191题解:此为多重背包用01和完全背包:

    #include<stdio.h>
    #include<string.h>
    int dp[102];
    int p[102],h[102],c[102];
    int n,m;
    void comback(int v,int w)//经费,重量。完全背包;
    {
        for(int i=v; i<=n; i++)
            if(dp[i]<dp[i-v]+w)
                dp[i]=dp[i-v]+w;
    }
    void oneback(int v,int w)//经费,重量;01背包;
    {
        for(int i=n; i>=v; i--)
            if(dp[i]<dp[i-v]+w)
                dp[i]=dp[i-v]+w;
    }
    int main()
    {
        int ncase,i,j,k;
        scanf("%d",&ncase);
        while(ncase--)
        {
            memset(dp,0,sizeof(dp));
            scanf("%d%d",&n,&m);//经费,种类;
            for(i=1; i<=m; i++)
            {
                scanf("%d%d%d",&p[i],&h[i],&c[i]);//价值,重量,数量;
                if(p[i]*c[i]>=n) comback(p[i],h[i]);
                else
                {
                    for(j=1; j<c[i]; j<<1)
                    {
                        oneback(j*p[i],j*h[i]);
                        c[i]=c[i]-j;
                    }
                    oneback(p[i]*c[i],h[i]*c[i]);
                }
            }
            printf("%d\n",dp[n]);
        }
        return 0;
    }


    只是用01背包,用二进制优化:

    #include <iostream>
    using namespace std;
    int main()
    {
        int nCase,Limit,nKind,i,j,k,  v[111],w[111],c[111],dp[111];
        //v[]存价值,w[]存尺寸,c[]存件数
        //在本题中,价值是米的重量,尺寸是米的价格
        int count,Value[1111],size[1111];
        //count存储分解完后的物品总数
        //Value存储分解完后每件物品的价值
        //size存储分解完后每件物品的尺寸
        cin>>nCase;
        while(nCase--)
        {
            count=0;
            cin>>Limit>>nKind;
            for(i=0; i<nKind; i++)
            {
                cin>>w[i]>>v[i]>>c[i];
                //对该种类的c[i]件物品进行二进制分解
                for(j=1; j<=c[i]; j<<=1)
                {
                    //<<左移1位,相当于乘2
                    Value[count]=j*v[i];
                    size[count++]=j*w[i];
                    c[i]-=j;
                }
                if(c[i]>0)
                {
                    Value[count]=c[i]*v[i];
                    size[count++]=c[i]*w[i];
                }
            }
            //经过上面对每一种物品的分解,
            //现在Value[]存的就是分解后的物品价值
            //size[]存的就是分解后的物品尺寸
            //count就相当于原来的n
            //下面就直接用01背包算法来解
            memset(dp,0,sizeof(dp));
            for(i=0; i<count; i++)
                for(j=Limit; j>=size[i]; j--)
                    if(dp[j]<dp[j-size[i]]+Value[i])
                        dp[j]=dp[j-size[i]]+Value[i];
    
            cout<<dp[Limit]<<endl;
        }
        return 0;
    }


    未优化的:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    int Value[105];
    int Cost[105];
    int Bag[105];
    int dp[105];
    
    int main()
    {
        int C,m,n;
        scanf("%d",&C);
        while(C--)
        {
            scanf("%d%d",&n,&m);
            for(int i = 1; i <= m; i++)
                scanf("%d%d%d",&Cost[i],&Value[i],&Bag[i]);
            memset(dp,0,sizeof(dp));
            for(int i=1; i<= m; i++)
                for(int j=1; j<=Bag[i]; j++)
                    for(int k=n; k>=Cost[i]; k--)
                        dp[k]=max(dp[k], dp[k-Cost[i]]+Value[i]);
            printf("%d\n",dp[n]);
        }
        return 0;
    }


    展开全文
  • 01背包:https://biancheng.love/problem/51/index 有n 种不同的物品,每个物品有两个属性,size 体积,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。 [cpp] view plain copy ...

    01背包:https://biancheng.love/problem/51/index

    有n 种不同的物品,每个物品有两个属性,weight重量,value 价值,现在给一个容量为 w 的背包,问最多可带走多少价值的物品。  

    int f[w+1];   //f[x] 表示背包容量为x 时的最大价值  
    for(int i = 1; i <= n;i++)
            {
                for(long long j = weight[i]; j <= m; j++)
                {
                    f[j] = max(f[j], f[j - weight[i]] + value[i]);
                    /*
                    long long tmp = f[j - weight[i]] + value[i];
                    if(f[j] < tmp)
                        f[j] = tmp;
                    */
                }
            }


    [cpp] view plain co

    V=10,N=3,c[]={3,4,5}, w={4,5,6}

    (1)背包不一定装满

          计算顺序是:从右往左,自上而下:因为每个物品只能放一次,前面的体积小的会影响体积大的

    (2)背包刚好装满    

          计算顺序是:从右往左,自上而下。注意初始值,其中-inf表示负无穷




    完全背包:https://biancheng.love/problem/100/index

    如果物品不计件数,就是每个物品不只一件的话,稍微改下即可  

    for (int i = 1; i <= n; i++)
            {
                for (int j = m; j >= weight[i]; j--)
                    f[j] = max(f[j], f[j - weight[i]] + value[i]);
            }


    [cpp] view pla

            f[w] 即为所求  
            初始化分两种情况:
            1、如果背包要求正好装满则初始化 f[0] = 0, f[1~w] = -INF;  

            2、如果不需要正好装满 f[0~v] = 0;  

    V=10,N=3,c[]={3,4,5}, w={4,5,6}

    (1)背包不一定装满

    计算顺序是:从左往右,自上而下:  每个物品可以放多次,前面的会影响后面的

    (2)背包刚好装满

    计算顺序是:从左往右,自上而下。注意初始值,其中-inf表示负无穷



    多重背包:https://biancheng.love/problem/122/index

    多重背包问题要求很简单,就是每件物品给出确定的件数,求可得到的最大价值  
             多重背包转换成 01 背包问题就是多了个初始化,把它的件数C 用二进制分解成若干个件数的集合,这里面数字可以组合成任意小于等于C的件数,而且不会重复,之所以叫二进制分解,是因为这样分解可以用数字的二进制形式来解释  
           比如:7的二进制 7 = 111 它可以分解成 001 010 100 这三个数可以组合成任意小于等于7 的数,而且每种组合都会得到不同的数  
           15 = 1111 可分解成 0001  0010  0100  1000 四个数字  
            如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成  7以内任意一个数,即1、2、4可以组合为1——7内所有的数,加上 0110 = 6 可以组合成任意一个大于6 小于等于13的数,比如12,可以让前面贡献6且后面也贡献6就行了。虽然有重复但总是能把 13 以内所有的数都考虑到了,基于这种思想去把多件物品转换为,多种一件物品,就可用01 背包求解了。 

    看代码:  
          

    [cpp] view plain copy
    1. int n;  //输入有多少种物品  
    2. int c;  //每种物品有多少件  
    3. int v;  //每种物品的价值  
    4. int s;  //每种物品的尺寸  
    5. int count = 0; //分解后可得到多少种物品  
    6. int value[MAX]; //用来保存分解后的物品价值  
    7. int size[MAX];  //用来保存分解后物品体积  
    8.   
    9. scanf("%d", &n);    //先输入有多少种物品,接下来对每种物品进行分解  
    10.   
    11. while (n--)     //接下来输入n中这个物品  
    12. {  
    13.     scanf("%d%d%d", &c, &s, &v);  //输入每种物品的数目和价值  
    14.     for (int k=1; k<=c; k<<=1)   //<<右移 相当于乘二  
    15.     {  
    16.         value[count] = k*v;  
    17.         size[count++] = k*s;  
    18.         c -= k;  
    19.     }  
    20.     if (c > 0)  
    21.     {  
    22.         value[count] = c*v;  
    23.         size[count++] = c*s;  
    24.     }  
    25. }  


    定理:一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1(k是满足n-2^k+1>0的最大整数)的形式,且1~n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。

    证明如下:

    (1) 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n,所以若干元素的和的范围为:[1, n];

    (2)如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示,这个很容易证明:我们把t的二进制表示写出来,很明显,t可以表示成n=a0*2^0+a1*2^1+…+ak*2^(k-1),其中ak=0或者1,表示t的第ak位二进制数为0或者1.

    (3)如果t>=2^k,设s=n-2^k+1,则t-s<=2^k-1,因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式,进而t可以表示成1,2,4,…,2^(k-1),s中某几个数的和(加数中一定含有s)的形式。

    (证毕!)


          

            现在用count 代替 n 就和01 背包问题完全一样了  

     

    可参考杭电2191(多重背包用01和完全背包)

    参考资料:http://blog.csdn.net/lyhvoyage/article/details/8545852


    展开全文
  • 题目 01背包 有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。 基本思路 这是最基础的背包问题,特点是:...

    题目    01背包 

    有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。

    基本思路

    这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

    用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

    f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。

    可以压缩空间,f[v]=max{f[v],f[v-w[i]]+v[i]}

    这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f [i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。

    注意f[v]有意义当且仅当存在一个前i件物品的子集,其费用总和为f[v]。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[v-1],这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以,由你自己来体会了。

     

    题目    完全背包

    有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。

    基本思路

    这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i,v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。这跟01背包问题一样有O(N*V)个状态需要求解,但求解每个状态的时间则不是常数了,求解状态f[v]的时间是O(v/c),总的复杂度是超过O(VN)的。

    将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度

    简单有效

    完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c<=c[j]且w>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小体积高的j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

    转为问题

    既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c 件,于是可以把第i种物品转化为V/c件体积及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。

    更高效的转化方法是:把第i种物品拆成体积为c*2^k、价值为w*2^k的若干件物品,其中k满足c*2^k<V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log(V/c))件物品,是一个很大的改进。但我们有更优的O(VN)的算法。* O(VN)的算法 这个算法使用一维数组,先看伪代码:<pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w};

    你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[v-c]。而完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[v-c],所以就可以并且必须采用v= 0..V的顺序循环。这就是这个简单的程序为何成立的道理。

    这个算法也可以以另外的思路得出。例如,基本思路中的状态转移方程可以等价地变形成这种形式:f[v]=max{f[v],f[v-c]+w},将这个方程用一维数组实现,便得到了上面的伪代码。

    总结

    完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。

    多重问题

    编辑

    题目

    有N种物品和一个容量为V的背包。第i种物品最多有n件可用,每件体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。

    基本算法

    这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n+1种策略:取0件,取1件……取 n件。令f[v]表示前i种物品恰放入一个容量为v的背包的最大权值,则:f[v]=max{f[v-k*c]+ k*w|0<=k<=n}。复杂度是O(V*∑n)。

     

     

    展开全文
  • 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解将那些物品装入背包可使总价值最大。  动态规划(DP):  1) 子问题定义:F[i][j]...

    http://blog.csdn.net/wumuzi520/article/details/7014559

    01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解将那些物品装入背包可使总价值最大。

            动态规划(DP):

            1) 子问题定义:F[i][j]表示前i件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。

            2) 根据第i件物品放或不放进行决策

                                                      (1-1)

            其中F[i-1][j]表示前i-1件物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值;

            而F[i-1][j-C[i]]+W[i]表示前i-1件物品中选取若干件物品放入剩余空间为j-C[i]的背包中所能取得的最大价值加上第i件物品的价值。

            根据第i件物品放或是不放确定遍历到第i件物品时的状态F[i][j]。

            设物品件数为N,背包容量为V,第i件物品体积为C[i],第i件物品价值为W[i]。

            由此写出伪代码如下:

         F[0][] ← {0}
    
         F[][0] ← {0}
    
         for i←1 to N
    
             do for k←1 to V
    
                 F[i][k] ← F[i-1][k]
    
                 if(k >= C[i])
    
                     then F[i][k] ← max(F[i][k],F[i-1][k-C[i]]+W[i])
    
         return F[N][V]
    


    以上伪代码数组均为基于1索引,及第一件物品索引为1。时间及空间复杂度均为O(VN)

            举例:表1-1为一个背包问题数据表,设背包容量为10根据上述解决方法可得到对应的F[i][j]如表1-2所示,最大价值即为F[6][10].

    表1-1背包问题数据表

    物品号i 1 2 3 4 5 6
    体积C 2 3 1 4 6 5
    价值W 5 6 5 1 19 7

    表1-2前i件物品选若干件放入空间为j的背包中得到的最大价值表

      0 1 2 3 4 5 6 7 8 9 10
    0 0 0 0 0 0 0 0 0 0 0 0
    1 0 0 5 5 5 5 5 5 5 5 5
    2 0 5 6 6 11 11 11 11 11 11 11
    3 0 5 5 10 11 11 16 16 16 16 16
    4 0 5 5 10 11 11 16 16 16 16 17
    5 0 5 5 10 11 11 19 24 24 29 30
    6 0 5 5 10 11 11 19 24 24 29 30

             很多文章讲背包问题时只是把最大价值求出来了,并没有把所选的是哪些物品找出来。本人在学习背包问题之前遇到过很多的类似问题,当时也是只求得了最大价值或最大和,对具体哪些物品或路径等细节也束手无策。再次和大家一起分享细节的求法。

            根据算法求出的最大价值表本身其实含有位置信息,从F[N][V]逆着走向F[0][0],设i=N,j=V,如果F[i][j]==F[i-1][j-C[i]]+W[i]说明包里面有第i件物品,同时j -= C[i],不管F[i][j]与F[i-1][j-C[i]]+W[i]相不相等i都要减1,因为01背包的第i件物品要么放要么不放,不管放还是不放其已经遍历过了,需要继续往下遍历。

    打印背包内物品的伪代码如下:

         i←N
    
         j←V
    
         while(i>0 && j>0)
    
             do if(F[i][j]=F[i-1][j-C[i]]+W[i])
    
                 then Print W[i]
    
                      j←j-C[i]
    
             i←i-1
    
    


     

    当然也可以定义一个二维数组Path[N][V]来存放背包内物品信息,开始时Path[N][V]初始化为0,当 F[i][j]==F[i-1][j-C[i]]+W[i]时Path[i][j]置1。最后通过从Path[N+1][V+1]逆着走向Path[0][0]来获取背包内物品。其中Path[0][]与Path[][0]为边界。
     
            加入路径信息的伪代码如下:
    


     

         F[0][] ← {0}
    
         F[][0] ← {0}
    
         Path[][] ← 0
    
         for i←1 to N
    
             do for k←1 to V
    
                 F[i][k] ← F[i-1][k]
    
                 if(k >= C[i] && F[i][k] < F[i-1][k-C[i]]+W[i])
    
                     then F[i][k] ← F[i-1][k-C[i]]+W[i]
    
                          Path[i][k] ← 1
    
         return F[N][V] and Path[][]
    
    


    打印背包内物品的伪代码如下:

         i←N
    
         j←V
    
         while(i>0 && j>0)
    
             do if(Path[i][j] = 1)
    
                 then Print W[i]
    
                      j←j-C[i]
    
             i←i-1
    
    


     

        在时间及空间复杂度均为O(NV)的情况下,利用Path[][]的方法明显比直接通过F[i][j]==F[i-1][j-C[i]]+W[i]来打印物品耗费空间,Path[][]需要额外的空间O(NV)但总空间复杂度不变仍为O(NV)。但下面要讲到的O(V)的空间复杂度的方法却不能利用关系式F [j]==F [j-C[i]]+W[i]而只能利用Path[][]进行标记.

    接下来考虑如何压缩空间,以降低空间复杂度。

    时间复杂度为O(VN),空间复杂度将为O(V)

            观察伪代码可也发现,F[i][j]只与F[i-1][j]和F[i-1][j-C[i]]有关,即只和i-1时刻状态有关,所以我们只需要用一维数组F[]来保存i-1时的状态F[]。假设i-1时刻的F[]为{a0,a1,a2,…,av},难么i时刻的F[]中第k个应该为max(ak,ak-C[i]+W[i])即max(F[k],F[k-C[i]]+W[i]),这就需要我们遍历V时逆序遍历,这样才能保证求i时刻F[k]时F[k-C[i]]是i-1时刻的值。如果正序遍历则当求F[k]时其前面的F[0],F[1],…,F[K-1]都已经改变过,里面存的都不是i-1时刻的值,这样求F[k]时利用F[K-C[i]]必定是错的值。最后F[V]即为最大价值。

    求F[j]的状态方程如下:

                                               (1-2)

    伪代码如下:

         F[] ← {0}
    
         for i ← 1 to N
    
             do for k ← V to C[i]
    
                 F[k] ← max(F[k],F[k-C[i]]+W[i])
    
         return F[V]
    


    同样,怎么求路径?

            利用前面讲到的Path[][]标记,需空间消耗O(NV)。这里不能用F [j]==F [j-C[i]]+W[i]来判断是因为一维数组并不能提供足够的信息来寻找二维路径。

            加入路径信息的伪代码如下:

         F[] ← {0}
    
         Path[][]←0
    
         for i←1 to N
    
             do for k←V to C[i]
    
                if(F[k] < F[k-C[i]]+W[i])
    
                     then F[k] ← F[k-C[i]]+W[i]
    
                          Path[i][k] ← 1
    
         return F[V] and Path[][]
    
    


     

    打印路径的伪代码和前面未压缩空间复杂度时的伪代码一样,这里不再重写。

    下面针对前面提到的表1-1提供两种方法的测试代码:

    #include <iostream>
    #include <cstring>
    #include "CreateArray.h"	//该头文件用于动态创建及销毁二维数组,读者自己实现
    using namespace std;


     

    //时间复杂度O(VN),空间复杂度为O(VN)


     

    int Package01(int Weight[], int Value[], int nLen, int nCapacity)
    {
    	int** Table = NULL;
    	int** Path = NULL;
    	CreateTwoDimArray(Table,nLen+1,nCapacity+1);	//创建二维数组
    	CreateTwoDimArray(Path,nLen+1,nCapacity+1);	//创建二维数组
    	
    	for(int i = 1; i <= nLen; i++)
    	{
    		for(int j = 1; j <= nCapacity; j++)
    		{
    			Table[i][j] = Table[i-1][j];
    			Path[i][j] = 0;
    			if(j >= Weight[i-1] && Table[i][j] < Table[i-1][j-Weight[i-1]]+Value[i-1])
    			{
    				Table[i][j] = Table[i-1][j-Weight[i-1]]+Value[i-1];
    				Path[i][j] = 1;
    			}
    		}
    	}
    
    	int i = nLen, j = nCapacity;
    	while(i > 0 && j > 0)
    	{
    		if(Path[i][j] == 1)
    		{
    			cout << Weight[i-1] << " ";
    			j -= Weight[i-1];
    		}
    		i--;
    	}
    	cout << endl;
    
    	int nRet = Table[nLen][nCapacity];
    	DestroyTwoDimArray(Table,nLen+1);	//销毁二维数组
    	DestroyTwoDimArray(Path,nLen+1);	//销毁二维数组
    	return nRet;
    }

     


    //时间复杂度O(VN),不考虑路径空间复杂度为O(V),考虑路径空间复杂度为O(VN)

    int Package01_Compress(int Weight[], int Value[], int nLen, int nCapacity)
    {
    	int * Table = new int [nCapacity+1];
    	memset(Table,0,(nCapacity+1)*sizeof(int));
    	int** Path = 0;
    	CreateTwoDimArray(Path,nLen+1,nCapacity+1);	//创建二维数组
    
    	for(int i = 0; i < nLen; i++)
    	{
    		for(int j = nCapacity; j >= Weight[i]; j--)
    		{
    			Path[i+1][j] = 0;
    			if(Table[j] < Table[j-Weight[i]]+Value[i])
    			{
    				Table[j] = Table[j-Weight[i]]+Value[i];
    				Path[i+1][j] = 1;
    			}
    		}	
    	}
    
    	int i = nLen, j = nCapacity;
    	while(i > 0 && j > 0)
    	{
    		if(Path[i][j] == 1)
    		{
    			cout << Weight[i-1] << " ";
    			j -= Weight[i-1];
    		}
    
    		i--;
    	}
    	cout << endl;
    	
    	int nRet = Table[nCapacity];
    	DestroyTwoDimArray(Path,nLen+1);	//销毁二维数组
    	delete [] Table;
    	return nRet;
    }
    

    本文部分内容参考“背包九讲”

    以下是我重写了上面的代码 进行了一部分简化:

    实现了上述的所有的伪码所描述的算法:

    #define N 5
    #define W 5
    int Weight[]={-1,4,2,1,3,4};
    int value[]={-1,19,29,11,23,11};
    int Path[N+1][W+1];
    int Table[N+1][W+1];
    int Table1[W+1];
    int Package01_1()
    {
    	memset(Table1,0,sizeof(int)*(W+1));
    	for(int i=0;i<N+1;i++)
    	{
    		for(int j=0;j<W+1;j++)
    		{
    			Path[i][j]=0;
    		}
    	}
    	for(int i=1;i<N;i++)
    	{
    		for(int j=W;j>=Weight[i];j--)
    		{
    			if(Table1[j]<Table1[j-Weight[i]]+value[i])
    			{
    				Table1[j]=Table1[j-Weight[i]]+value[i];
    				Path[i][j]=1;
    			}
    		}
    	}
    	int i=N,j=W;
    	cout<<"该进版本:"<<endl;
    	while(i>0&&j>0)
    	{
    		if(Path[i][j]==1)
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    	cout<<endl;
    	return Table1[W];
    }
    
    
    ///重量数组, 价值数组,数据个数,横坐标长度
    int Package01()
    {
    	for(int i=0;i<N+1;i++)
    	{
    		for(int j=0;j<W+1;j++)
    		{
    			Table[i][j]=-1;
    			Path[i][j]=0;
    		}
    	}
    	for(int i=0;i<W+1;i++)
    	{
    		Table[0][i]=0;
    	}
    	for(int j=0;j<N+1;j++)
    	{
    		Table[j][0]=0;
    	}
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=W;j++)
    		{
    			if(j<Weight[i])
    			{
    				Table[i][j]=Table[i-1][j];
    			}
    			else
    			{
    				int t1=Table[i-1][j];
    				int t2=Table[i-1][j-Weight[i]]+value[i];
    				if(t2>t1)
    					Path[i][j]=1;
    				Table[i][j]=t1>t2?t1:t2;
    			}
    		}
    	}
    	return Table[N][W];
    }
    void Print()
    {
    	int i=N;
    	int j=W;
    	while(i>0&&j>0)
    	{
    		if(Path[i][j]==1)
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    }
    void Print_1()
    {
    	int i=N;
    	int j=W;
    	while(i>0&&j>0)
    	{
    		if(Table[i-1][j-Weight[i]]+value[i]==Table[i][j])
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    }
    
     int main()
     {
    	 cout<<"没有改进版本:"<<endl;
    	 cout<<Package01()<<endl;
    	Print();
    	 cout<<endl;
    	 Print_1();
    	 cout<<endl;
    
    	 cout<<Package01_1()<<endl;
    	 return 0;
     }
    
    
    


     


    #define N 5
    #define W 5
    int Weight[]={-1,4,2,1,3,4};
    int value[]={-1,19,29,11,23,11};
    int Path[N+1][W+1];
    int Table[N+1][W+1];
    int Table1[W+1];
    int Package01_1()
    {
    	memset(Table1,0,sizeof(int)*(W+1));
    	for(int i=0;i<N+1;i++)
    	{
    		for(int j=0;j<W+1;j++)
    		{
    			Path[i][j]=0;
    		}
    	}
    	for(int i=1;i<N;i++)
    	{
    		for(int j=W;j>=Weight[i];j--)
    		{
    			if(Table1[j]<Table1[j-Weight[i]]+value[i])
    			{
    				Table1[j]=Table1[j-Weight[i]]+value[i];
    				Path[i][j]=1;
    			}
    		}
    	}
    	int i=N,j=W;
    	cout<<"该进版本:"<<endl;
    	while(i>0&&j>0)
    	{
    		if(Path[i][j]==1)
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    	cout<<endl;
    	return Table1[W];
    }
    
    
    ///重量数组, 价值数组,数据个数,横坐标长度
    int Package01()
    {
    	for(int i=0;i<N+1;i++)
    	{
    		for(int j=0;j<W+1;j++)
    		{
    			Table[i][j]=-1;
    			Path[i][j]=0;
    		}
    	}
    	for(int i=0;i<W+1;i++)
    	{
    		Table[0][i]=0;
    	}
    	for(int j=0;j<N+1;j++)
    	{
    		Table[j][0]=0;
    	}
    	for(int i=1;i<=N;i++)
    	{
    		for(int j=1;j<=W;j++)
    		{
    			if(j<Weight[i])
    			{
    				Table[i][j]=Table[i-1][j];
    			}
    			else
    			{
    				int t1=Table[i-1][j];
    				int t2=Table[i-1][j-Weight[i]]+value[i];
    				if(t2>t1)
    					Path[i][j]=1;
    				Table[i][j]=t1>t2?t1:t2;
    			}
    		}
    	}
    	return Table[N][W];
    }
    void Print()
    {
    	int i=N;
    	int j=W;
    	while(i>0&&j>0)
    	{
    		if(Path[i][j]==1)
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    }
    void Print_1()
    {
    	int i=N;
    	int j=W;
    	while(i>0&&j>0)
    	{
    		if(Table[i-1][j-Weight[i]]+value[i]==Table[i][j])
    		{
    			cout<<i<<" ";
    			j-=Weight[i];
    		}
    		i--;
    	}
    }
    
     int main()
     {
    	 cout<<"没有改进版本:"<<endl;
    	 cout<<Package01()<<endl;
    	Print();
    	 cout<<endl;
    	 Print_1();
    	 cout<<endl;
    
    	 cout<<Package01_1()<<endl;
    	 return 0;
     }
    
    
    


    本文部分内容参考“背包九讲”本文部分内容参考“背包九讲”本文部分内容参考“背包九讲”

     

    展开全文
  • 背包问题

    千次阅读 多人点赞 2015-06-22 20:00:05
    背包问题
  • 问题描述 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8 i...
  • 01背包,完全背包,多重背包问题总结

    千次阅读 多人点赞 2019-03-21 21:51:47
    背包问题是很经典的一类题目,解决问题的重点是动态规划的状态转换。用了很久才大概弄明白了三种问题的解决方法,今天做一下总结。 01背包 首先是01背包,即给定N个物品,给出它们的价值和所占用的体积,再给定一个...
  • 01背包问题是背包类问题中最基本的问题,其它各类背包问题都是在其基础上演变而来 牢记01背包的特点:每一件物品至多只能选一件,即在背包中该物品数量只有0和1两种情况 装入背包,如果装不下就换下一个,直到包满...
  • 背包问题-01背包问题

    2019-03-15 16:46:55
    背包容积为 5 物品数量为 4 物品的体积分别为 {0, 1, 2, 3, 4} 物品的价值分别为 {0, 2, 4, 4, 5} 思路 定义一个二位数组 int [][] f = new int[n+1][V+1]f[i][j]就表示在1~i个物品中选取体积小于V的情况的最大...
  • 01背包问题和完全背包问题

    万次阅读 多人点赞 2014-08-27 10:27:28
    在hihocoder上面两期的题目,一个01背包问题,一个完全背包问题。总结一下!
  • 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为C1,C2,…,Cn,与之相对应的价值为W1,W2,…,Wn.求解将那些物品装入背包可使总价值最大。  1) 子问题定义:F[i][j]表示前i件物品中选取若干...
  • 动态规划之01背包问题(最易理解的讲解)

    万次阅读 多人点赞 2012-07-06 17:09:37
    01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi...
  • 背包问题详解:01背包、完全背包、多重背包

    万次阅读 多人点赞 2017-03-17 11:47:48
    参考链接: http://www.cnblogs.com/fengty90/p/3768845.html http://blog.csdn.net/mu399/article/details/7722810 http://blog.csdn.net/xiaowei_cqu/article/details/8191808 ...
  • 01背包问题

    千次阅读 热门讨论 2017-05-18 17:43:40
    01背包问题
  • 01普通背包和01背包问题

    千次阅读 2017-04-04 11:10:17
    背包问题: 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 c[i],得到的 价值是 w[i]。求解将哪些物品装入背包可使价值总和最大。 最普通的背包问题,对于每个物品,可选择放或者不放。 所以状态...
  • 1 牛牛的背包问题 牛牛的背包问题 —— 牛客网 问题描述: 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。 牛牛想知道在总体...
  • 1. 0-1背包问题 1.1 题目描述 有一个包和n个物品,包的容量为m,每个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,能够得到的最大价值是多少?[对于每个物品...
  • 背包问题01背包

    2015-07-02 18:57:23
    背包问题:给定一组物品,每个物品的费用和价值是不同的,求怎样选择物品使得在不超过限定总费用的条件下最后的总价值最大。 01背包是背包系列问题的基础,其解决问题的思想很重要。01背包问题限定每个物品的个数是1...
  • P01: 01背包问题

    千次阅读 2012-01-05 15:10:46
    P01: 01背包问题 问题描述 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择...
  • 最基本的是01背包问题,题目一般类似:“在一定数目物品内,挑选总重量不超过一定数目的物品,其中每个物品只能选一次,求背包内物品价值的最大值或者最小值”,从名字就可以看出,要么选0个,要么选1个。...
  • 01背包问题VS完全背包问题

    千次阅读 2019-08-19 21:44:05
    01背包问题: 每个物品只能选择一次,给定背包的最大承重量total和每个物品i的重量weight[i]和价值value[i],求背包可以装下的最大价值 #include<iostream> #include<vector> using namespace std; ...
  • 01背包 0-1背包问题是指每一种物品都只有一件,可以选择放或者不放。 方法一 V(i,j)表示前i种物品恰放入一个容量为j的背包的最大价值,因此状态转移方程: j&amp;lt;w(i) V(i,j)=V(i-1,j) j&amp;...
  • 转自: http://apps.hi.baidu.com/share/detail/14968747 P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
  • 回溯法-经典 01背包问题

    万次阅读 2016-06-22 11:37:08
    经典问题:给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??分析1、如上图碰到一组数据,有两种可能:选或者不选,在树种...
  • 枚举法 背包问题01

    千次阅读 2014-12-23 16:08:06
    // beibao01_穷举法 // // Created by 瑛峰 on 14/12/23. // Copyright (c) 2014年 angran. All rights reserved. // #include #include #include #define MAX 100 using namespace s
  • 01背包问题 有N种物品,每种物品的数量为C1,C2……Cn。从中任选若干件放在容量为W的背包里,每种物品的体积为W1,W2……Wn(Wi为整数),与之相对应的价值为P1,P2……Pn(Pi为整数)。求背包能够容纳的最大价值。...

空空如也

1 2 3 4 5 ... 20
收藏数 39,685
精华内容 15,874
关键字:

背包问题