详解--背包九讲

秒速五厘米 2022-06-11 04:23 130阅读 0赞

背包问题是典型的动态规划问题，满足当前状态的值只跟前一状态有关，所以我们用动态规划的思想对下面所出现的背包问题分析求解。

**1:  0-1背包**

0-1背包是最基础的背包问题，就是给出一个容量v的背包和n个价值为 w\[ i \] 和数量为c \[ i \]的物品，问你怎么装才能使得背包的价值最大。

假设我们使用dp \[ i \]\[ v \] 表示前 i 件物品放入 容量 v 的背包中的最大价值；根据dp的思想，回朔到前一状态，就是

dp \[ i -1 \] \[ v \]或者dp\[ i-1 \] \[ v-c \[ i \] \] + w \[ i \] 中的最大值，这样动态转移方程为dp\[i\]\[v\]=max(dp\[i-1\]\[v\],dp\[i-1\]\[v-c\[i\]\]+w\[i\]),意思就是我们只有两种选择，这件物品放还是不放，放入后价值大还是不放这件物品的价值大。运用两次循环就可以求的最大的价值。

可能很多人有这样的疑问，我每次有两种选择，肯定大多数情况下能够装进去的话肯定是装进去的价值大，那么我装进去之后假如后面有一个价值更大的但是由于前一个的装进去而装不进去了，那么是不是错了呢？其实不是的，

看看转移方程:dp\[i\]\[v\]=max(dp\[i-1\]\[v\],dp\[i-1\]\[v-c\[i\]\]+w\[i\]),如果出现一个更大的，而占背包面积更大的话，他会出现dp\[i-1\]\[v-c\[i\]\]+w\[i\]比dp\[ i-1 \]\[ v \] 大二正确转移。这就dp的一个很重要的方面就是从那边开始转移！

但是我们发现，其实不用二维的数组，循环两次也可以实现，直接用dp \[ v \] 表示价值则dp \[ v \]= max ( dp\[ v \] , dp\[ v-c \[ i \] \] + w\[ i \] )。

下面的过程：

for(int i=0;i<n;i++)  
    for(int j=v;j>=c\[i\];j–)  
    dp\[v\]=max\{dp\[v\]，dp\[v-c\[i\]\]+w\[i\]\};

下面看一道nyoj上最基础的0-1 背包问题：[http://acm.nyist.net/JudgeOnline/problem.php?pid=289][http_acm.nyist.net_JudgeOnline_problem.php_pid_289] 模板题，代码：

#include<stdio.h>#include<string.h>#define max(a,b) a>b?a:b
    int dp[1100];
    int main()
    {
        int num,lar,i,j;
        while(scanf("%d%d",&num,&lar) && !(num==0 && lar==0))
        {
            int c,w;
            memset(dp,0,sizeof(dp));
            for(i=0;i<num;i++)
            {
                scanf("%d%d",&c,&w);
                for(j=lar;j>=c;j--)
                {
                    dp[j]=max(dp[j],dp[j-c]+w);
                }
            }
            printf("%d\n",dp[lar]);
        }
        return 0;
    }

还有hdoj上的0-1背包的变形题： [http://acm.hdu.edu.cn/showproblem.php?pid=2955][http_acm.hdu.edu.cn_showproblem.php_pid_2955]

这个题很有意思， 将小偷计划要偷的钱的总数作为背包的容量，然后每个银行的存款就作为各个物品的重量，每个银行小偷的逃跑率就作为每个物品的价值，这样就转化为01背包问题了。至于为什么不可以用题目给的被抓获的概率作为价值，是因为小偷被抓与否的计算方法，不是将每个银行小偷被抓的概率相乘，概率论的基本知识，所以要以逃跑率作为价值。定义数组 F\[j\]为偷到j万元的时候，逃跑的概率，那么状态方程如下：F\[j\]=max\{F\[j\],F\[j-m\[i\]\]\*g\[i\]\}，其中m\[i\]是第i个银行的存款，g\[i\]是在该银行偷窃后逃跑的概率。

2：完全背包

既然看了0-1背包，完全背包相对也好理解，0-1背包是每次只能选一个物品，而完全背包是可以选任意多个，意思就是给出一个容量v的背包和n个体积为c \[ i \]和价值为w\[ i \]的物品，每件可以放多次，求其背包的最大价值容量。

我们顺着0-1背包的思想，既然选择可以是多件那么dp\[ i \]\[ v \]=max( dp\[ i-1 \]\[ v \], dp\[ i-1 \]\[ v- k\*c\[ i \] \] + k\*w\[ i \] );这是在0-1背包的基础上得来的，就是多了一次k的循环，时间复杂度较高，我很尝试对其进行改进。

完全背包的一个很有效的优化，就是对于价值大/体积小的物品和价值小/体积大的物品，我们当然优先选择物美价廉的，因为每件可以选择n次，我们当然要尽可能地的选择价值体积比大的，还有价值体积比相等的，我们可以很大胆的直接把其中体积大的直接舍去，这样对于数据较大的题来说可以很大的优化，当然不能排除特殊情况。

对于上面的动态转移方程，我们根据0-1背包的思想转化为一维的，就是这样一个过程求解：

for(int i=0;i<m;i++)  
        \{  
            for(int j=0;j<n\[i\];j++)  
            \{  
                for(int k=v;k>=w\[i\];k–)  
                    dp\[k\]=max(dp\[k\],dp\[k-w\[i\]\]+c\[i\]);  
            \}  
        \}

不用说，这样三层循环下来一般的题都会超时；我们看看上面的操作；j从v—>c\[i\],然后k从0–>v/c\[i\]，那么我们为什么不直接让j从0–>v；看看下面；

for(int i=0;i<n;i++)  
         for(int j=c\[i\];j<=v;j++)  
                dp\[j\]=min(dp\[j\],dp\[j-c\[i\]+w\[i\]);

记得0-1背包的j的循环式从v–>0的。我们为什么要这样呢，就是为了控制每件物品只选择一次，我们在脑子中模拟一下这个过程，或者手动模拟一下，那么这个是从0–>v的，正好就能够让每件物品可以多次的选择，从0开始，每增加都够一个c\[i\]放入一件，知道背包放不进去。我们可以运用二位数组用第一个动态方程进行模拟，会发现它的巧妙性。

还有一个就是恰好放入的问题，有点题要求恰好把背包放满，这该怎么处理呢，我们可以让dp初始为无穷小，这样要是不能放满的话dp【v】的值也会无穷小，我们就可以判断其装满了没有，当然这个在所有的背包问题中都有用。运用的时候要灵活，比如下面这一道题。

下面看一道完全背包模板题：[http://acm.hdu.edu.cn/showproblem.php?pid=1114][http_acm.hdu.edu.cn_showproblem.php_pid_1114]

直接代码：

#include <cstdio>#include <cstring>#define min(a,b) a>b?b:a
    
    int main()
    {
        int T,s,e,m,n;
        int dp[250010],c[510],w[510];
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&s,&e);
            m=e-s;
            memset(dp,999999,sizeof(dp));
            dp[0]=0;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
                scanf("%d%d",&w[i],&c[i]);
            for(int i=0;i<n;i++)
            {
                int j;
                for(j=c[i];j<=m;j++)
                    dp[j]=min(dp[j],dp[j-c[i]]+w[i]);
            }
            if(dp[m]>900000)
                printf("This is impossible.\n");
            else
                printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);
        }
        return 0;
    }

3：多重背包

多重背包就是在0-1和完全背包的结合；即给你一个容量为v的背包和n个价值w，体积c，数量num的背包，让你选择装入物品使得背包的容量最大。

这样我们可以马上想到用0-1背包解决；把这个每个的数量为num的的物品看成是num个物品。就是把每一个num加起来的和就是物品的总数量，然后就转化为0-1背包去解决，这样一般的题目是可以的，但是如果每一个物品的数量都很多的话我们就没有办法知道dp\[\]数组开多大了，运算也会很慢。。下面看转化0-1背包的代码：

for(int j=1; j<=c; j++)    
\{    
        cost\[w\] = p;    
        heavy\[w++\] = h;    
\}

还有一种方法就是转化为多重背包的思想，还是上面的多重背包的动态转移方程，d\[v\]=max(dp\[v\],dp\[v-k\*c\]+k\*w)当然这里的k就有限制了就是从0–>num.这样做的话用三层循环，时间下来的话会超时，下面贴出转化为完全背包的思想解决的核心代码：

for(int i=0;i<m;i++)
            {
        
                for(int j=0;j<num;j++)
                {
        
                    for(int k=v;k>=c;k--)
                        dp[k]=max(dp[k],dp[k-c]+w);
                }
            }

二分优化：上面两种方法虽然都可以解决问题，但是时间上都不是很理想，那么我们能不能这么想呢，既然有num个物品。我们把这num这物品分割，这里用到一个思想就是所有的数都可以用（2^0,2^1,2^3…..2^n）这些说的和组合起来表示，这就为我们解决问题提供了思路，背包中要放入一件物品，我们看看这一件物品的num个放入背包的话能不能装满，如果刚好装满或者超出了我们就可完全转化为多重背包。如果装不满的话我们就可以对物品分割，分割成每一个之后吧、把每一个放入解决。这里放每一个当然是0-1背包了。这样就是多重背包的最大优化了、如果还想优化的话就就分别对他们在用0-1和完全背包的优化思想进行优化。

总结：多重背包就是一个对0-1背包和完全背包的思想的结合运用，所以就要求对基础的0-1背包首先完全理解并熟练，其实前面这三种背包问题都是基础。学背包的问题我们能够体会到优化的思想，一道题我们不断的可以优化优化，不断细化优化，当然优化到一定程度也就要求代码能力了。所以说代码能力还是基础啊、是练出来的，代码之路漫漫。。。好好修炼吧。

下面来看一道多重背包的模板题：[http://acm.hdu.edu.cn/showproblem.php?pid=2191][http_acm.hdu.edu.cn_showproblem.php_pid_2191]

下面就直接上二分优化的代码：其他的我们可以结合上面的讲解自己尝试写出来：

#include <iostream>#include <cstring>#define max(a,b) a>b?a:b
    using namespace std;
    
    int f[110];
    
    void one(int cost , int w, int m)
    {
        for(int i=cost ; i<=m; i++)
            f[i] = max(f[i] , f[i - cost ]+w);
    }
    void zero_one(int m ,int w, int cost)
    {
        for(int i=m; i>=cost; i--)
            f[i]=max(f[i],f[i-cost]+w);
    }
    int main()
    {
        int T;
        cin >> T;
        while( T --)
        {
            int m,n;
            cin>> m >> n;
            for(int i=0; i<=m; i++)
                f[i] = 0 ;
            for(int i=0; i<n; i++)
            {
                int cost , w, nk;
                cin>> cost >> w >> nk;
                if(cost * nk >= m) one(cost , w  , m);
                else
                {
                    int k = 1;
                    while( k < nk)
                    {
                        zero_one(m,k*w,k*cost);
                        nk -= k;
                        k *= 2;
                    }
                    zero_one(m,nk*w,nk*cost);
                }
            }
            cout << f[m] << endl;
        }
        return 0;
    }

4：三种背包的结合

所谓三种背包的结合就是给出容量v的背包和一些物品，这些物品的重量c和价值w。这些物品有的有无数件，有的一件，有的是有限n件。要求我们求出怎么装能够使得价值最大。就像这道题目：[http://oj.hsfz.net.cn/JudgeOnline/problem.php?id=1423][http_oj.hsfz.net.cn_JudgeOnline_problem.php_id_1423]

怎么做及方程就不用说了，因为就是对上面三种的组合运用，这就要求我们充分的运用前面所学的三种背包，怎么选择装入的次序，这样的组合起来难度就大大的增大了，我写了这道题，但是没过，应该是动态的次序没有对，谁做出来了可以提醒一下，非常感谢。

5：二维费用的背包问题

就是给出一个可装容量为v，体积为u的背包，给出一些物品的价值w，重量c和所占体积l，让我们求怎样装使得装入的价值最大。这种问题最常见的变形是给出最多能取M件物品这样限制，如果要求恰好区M件物品，我们可以用dp\[0–v\]\[M\]循环去求。

我们根据前面背包问题可以很容易的写出动态转移方程，即dp\[i\]\[v\]\[u\]=max(dp\[i\]\[v\]\[u\],dp\[i-1\]\[v-c\]\[u-l\]);当然我们也是可以优化减去一维来解决这个问题，即dp\[v\]\[u\]=max(dp\[v\]\[u\],dp\[v-c\]\[u-l\]);这样，多加一维的循环就可以解决这个问题了，其实背包问题的思想都是一样的，只要对前面的基础问题能够深刻的理解了，后面的这写可以自己推出来。

下面看一道二维费用的题目：[http://acm.hdu.edu.cn/showproblem.php?pid=2159][http_acm.hdu.edu.cn_showproblem.php_pid_2159]

典型的限制数量二维背包模板题，代码：

#include <iostream>#include <cstring>
    using namespace std;#define max(a,b) a>b?a:b
    int a[105],b[105],dp[105][105];
    int main()
    {
        int n,m,k,s,ok;   //经验，忍耐度，怪种，最多杀怪数,每只怪得到经验和减掉的忍耐度
        while(cin>>n>>m>>k>>s)
        {
            for(int i=0;i<k;i++)
            {
                cin>>a[i]>>b[i];
            }
            memset(dp,0,sizeof(dp));
             for(int i = 0; i<k; i++)
            {
                for(int j = b[i]; j<=m; j++)//忍耐度
                {
                    for(int l = 1; l<=s; l++)  //限制杀怪数目
                        dp[j][l]=max(dp[j][l],dp[j-b[i]][l-1]+a[i]);
                }
            }
            ok=-1;
            for(int i=1;i<=m;i++)
            {
                if(ok!=-1) break;
                if(dp[i][s]>=n)
                    {
                        ok=m-i;
                        break;
                    }
            }
            if(ok==-1)
                cout<<-1<<endl;
            else
                cout<<ok<<endl;
        }
        return 0;
    }

6：分组背包问题

分组背包问题就是给出一个容量为v的背包，给出m组物品，每组物品中有若干件其价值w和体积c。每组物品中只能选择一件，求使得不超过背包容量的最大价值。

这样我们一分析很容易就想到我们选择m组物品时每组都选择器价值体积比最大的不就OK了吗，这也是上面2中的一个有效的优化的思想，但是仔细分析我们发现，这种优化在这里确实很有效！

既然每组物品只能选一件，我们用dp\[k\]\[v\]表示前k组物品占容积v所能得到的最大价值。则动态转移方程为dp\[k\]\[v\]=max( dp\[k-1\]\[v\],dp\[k-1\]\[v-c\]+w );就是0-1背包的思想。有了动态转移方程我们就考虑怎么实现呢，也就是比0-1多了一重每组物品中选择最优或者不选的过程，我们把这一层循环放在最里层就可以了，在经典背包博客中看到的是放在第二层的，但是我尝试了一些题目发现测试数据能过，但是wa、、这样的不同我正在思考中。哪位大牛看到希望能为我解答。模板就是这样：

for(int i=1;i<=n;i++)  
        \{  
            for(int k=m;k>0;k–)  
            \{  
                for(int j=1;j<=k;j++)  
                    dp\[k\]=max(dp\[k\],dp\[k-j\]+map\[i\]\[j\]);  
            \}  
        \}

下面看一道模板题目：[http://acm.hdu.edu.cn/showproblem.php?pid=1712][http_acm.hdu.edu.cn_showproblem.php_pid_1712]

代码：

/*分组背包问题，刚开始看大牛背包博客让j的循环在k的循环的前面，测试数据过了但是wa、看了别人的代码改成现在这样就过了
    */#include <cstdio>#include <cstring>#define max(a,b) a>b?a:b
    int dp[100*101],map[105][105],c[105];
    int main()
    {
        int m,n;
        while(~scanf("%d%d",&n,&m) && (m+n))   //n课程。m表示有的天数
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    scanf("%d",&map[i][j]);
                }
            }
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++)
            {
                for(int k=m;k>0;k--)
                {
                    for(int j=1;j<=k;j++)
                        dp[k]=max(dp[k],dp[k-j]+map[i][j]);
                }
            }
            printf("%d\n",dp[m]);
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_289]: http://acm.nyist.net/JudgeOnline/problem.php?pid=289
[http_acm.hdu.edu.cn_showproblem.php_pid_2955]: http://acm.hdu.edu.cn/showproblem.php?pid=2955
[http_acm.hdu.edu.cn_showproblem.php_pid_1114]: http://acm.hdu.edu.cn/showproblem.php?pid=1114
[http_acm.hdu.edu.cn_showproblem.php_pid_2191]: http://acm.hdu.edu.cn/showproblem.php?pid=2191
[http_oj.hsfz.net.cn_JudgeOnline_problem.php_id_1423]: http://oj.hsfz.net.cn/JudgeOnline/problem.php?id=1423
[http_acm.hdu.edu.cn_showproblem.php_pid_2159]: http://acm.hdu.edu.cn/showproblem.php?pid=2159
[http_acm.hdu.edu.cn_showproblem.php_pid_1712]: http://acm.hdu.edu.cn/showproblem.php?pid=1712