二维费用的背包问题是背包问题的一个简单的常见扩展。

        二维费用的背包问题的一般描述为：对于装入背包的每个物品i，都具有两种不同的代价 C1[i]与C2[i]，选择物品i装入背包时必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（上限）V1和V2，物品i装入可获得的价值为P[i]。问在每个物品只能装入一次的条件下，怎么选择物品可得到最大的价值。

        其解题思路一般为：

        令 f[i][j][k]表示前i个物品在代价1为j，代价2为k的条件下装入背包的可获得的最大值。

        根据0/1背包问题有

            f[i][j][k] = max { f[i−1][j][k] , f[i−1][j−C1[i]][k−C2[i]] + P[i]}

        同样可以将数组由三维数组优化为二维数组，即

            f[j][k] = max { f[j][k] , f[j−C1[i]][k−C2[i]] + P[i]}

        编写代码时，一般采用如下的3重循环：

​         for (i=1;i<=n;i++)           // 装入背包的物品个数为n

              for (j=V1;j>=C1[i];j--)

                     for (k=V2;k>=C2[i];k--)

                     {

                           f[j][k]=max(f[j][k],f[j-C1[i]][k-C2[i]]+P[i]);

                   }

        所求最大价值为f[V1][V2]。 

【例1】游戏项目

问题描述

一天小明来到欢欢娱乐城游玩，游乐场的游戏项目真多呀。每个游戏项目需要花费小明的一些时间和一些金钱。

由于小明的时间和金钱是有限的，所以他很难将所有游戏项目都玩一遍。他决定选择一些项目进行游玩，并且每个项目最多玩一次。他想知道在不超过自己所剩时间和金钱的范围内，最多可以玩多少个游戏项目？

输入

第一行三个整数n,M,T，表示一共有n（1≤n≤100）个游戏项目， 小明的手上还剩M（0≤M≤200）元，他有T（0≤T≤200）分钟时间。

第2~n+1行 mi, ti 表示玩第i个游戏项目所需要的金钱和时间。

输出

一行，一个数，表示小明最多可以玩的游戏项目的个数。

输入样例

6 10 10

1 1

2 3

3 2

2 5

5 2

4 3

输出样例

4

         （1）编程思路。

          玩游戏项目i时，需要付出的两种代价分别为时间t[i]和金钱m[i]，直接套用二维费用背包问题的模板即可。

          （2）源程序。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else  return b;
}
int main()
{
    int f[205][205]={0};
    int m[101],t[101];
    int n,M,T;
    scanf("%d%d%d",&n,&M,&T);
    int i,j,k;
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&m[i],&t[i]);
    }
    for (i=1;i<=n;i++)
      for (j=M;j>=m[i];j--)
        for (k=T;k>=t[i];k--)
        {
            f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1);
        }
    printf("%d\n",f[M][T]);
    return 0;
}

【例2】L国的战斗之间谍

问题描述

L国即将与I国发动战争！！L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

你现在有N个人选，每个人都有这样一些数据：A（能得到多少资料）、B（伪装能力有多差）、C（要多少工资）。已知敌人的探查间谍能力为M（即去的所有人B的和要小于等于M）和手头有X元钱，请问能拿到多少资料？

输入

输入第1行为三个整数：N、M、X（1≤N≤100，1≤M≤1000，1≤X≤1000）。

之后有N行，每行包括三个整数：Ai、Bi、Ci，表示第i个人选相关数据。

输出

能得到的资料总数。

输入样例

3 10 12

10 1 11

1 9 1

7 10 12

输出样例

11

          （1）编程思路。

         选择第i个人选时，需要付出的两种代价分别为伪装能力b[i]和需要的经费c[i]，选择该人选后，可获得的资料为a[i]，直接套用二维费用背包问题的模板即可。

         （2）源程序。

#include <stdio.h>
int f[1001][1001]={0};
int main()
{
    int n,m,x;
    scanf("%d%d%d",&n,&m,&x);
    int a[101],b[101],c[101];
    int i,j,k;
    for (i=1;i<=n;i++)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (i=1;i<=n;i++)
    {
        for (j=m;j>=b[i];j--)
            for (k=x;k>=c[i];k--)
             if (f[j][k]<f[j-b[i]][k-c[i]]+a[i])
                f[j][k]=f[j-b[i]][k-c[i]]+a[i];
    }
    printf("%d\n",f[m][x]);
    return 0;
}

        将上面的源程序提交给洛谷题库P1910 L国的战斗之间谍（https://www.luogu.com.cn/problem/P1910），测评结果为“Accepted”。

 【例3】三角牧场

问题描述

奶牛牧场建筑师I.M.Hei负责创建一个三角形的牧场，周围有漂亮的白色围栏。她被提供了N（3<=N<=40）个围栏段，每个围栏段的长度为整数Li（1<=Li<=40）。她用这些围栏段来组成三角形牧场的三条边，使得该牧场的放牧面积最大。

输入

第1行：单个整数N

第2行~N+1行：每行都有一个整数，表示一个围栏段的长度。长度不一定是唯一的。

输出

输出一行为一个整数，该整数是最大可能封闭区域的面积乘以100的截断整数表示。如果不能围成三角形，则输出-1。

输入样例

5

1

1

3

3

4

输出样例

692

         （1）编程思路。

        把边的长度看成费用。三角形中的某条边i看作第一维费用，另一条边j看作是第二维费用，背包容量为总长sum的一半（三角形任意一条边都不可能比周长的一半大），则第三边为sum-i-j。给定的围栏看成装入背包的物品。

        设f[i][j]表示由这些围栏是否可以构成一条边长为i，另一条边长为j。初始时除f[0][0]=1外，其余元素全部为0。

       通过二维0/1背包找出所有满足的i,j（即f[i][j]=1），枚举求出最大面积即可。

        （2）源程序。

#include <stdio.h>
#include <string.h>
#include <math.h>
int f[805][805];
int main()
{
    int len[45];
    int n;
    while (scanf("%d",&n) !=EOF)
    {
        int sum=0;
        int i,j,k;
        for (i=1; i<=n; i++)
        {
           scanf("%d",&len[i]);
           sum+=len[i];
        }
        memset(f,0,sizeof(f));
        f[0][0]=1;
        int mid=sum/2;
        for (i=1; i<=n; i++)
           for (j=mid; j>=0; j--)
              for (k=mid; k>=0; k--)
              {
                  if ((j>=len[i]&& f[j-len[i]][k])||(k>=len[i]&&f[j][k-len[i]]))
                     f[j][k]=1;
              }
        int ans=-1;
        for (i=mid; i>0; i--)                       // 通过枚举可构成三角形的两条边，找到最大面积
           for (j=mid; j>0; j--)
              if (f[i][j])
              {
                  k=sum-i-j;                        // 第3条边的长度
                  if (i+j>k && i+k>j && j+k>i)      // 两边之和大于第三边
                  {
                      double p=sum/2.0;
                      double x=sqrt(p*(p-i)*(p-j)*(p-k));
                      if (x*100>ans)
                         ans=x*100;
                  }
              }
        printf("%d\n",ans);
    }
    return 0;
}

        将上面的源程序提交给北大OJ题库POJ 1948 Triangular Pastures（http://poj.org/problem?id=1948），可以Accepted。

 【例4】铺放线段

问题描述

有n条线段，每条线段只能放在数轴上的一个特定位置，并且第i根线段有如下几个属性：Xi（该线段放在数轴上的起点），Wi（该线段长度），Fi（你若使用该线段你能获得的价值），Ci（你若使用该线段你所需要的费用）。现在让你从中选出一些线段，使得这些线段能够铺满数轴上的区间[0,L]，并且所花费用和不超过B，同时要使你收获的价值尽量大，请你找到这个方案。

输入

第一行三个整数 L（1 ≤L≤1,000），n（1≤N≤10,000），B（1 ≤B≤1,000）。

接下来n行，每行四个整数 Xi，Wi，Fi，Ci，表示第i根线段的四个属性。

输出

一个整数，表示你能获得的最大价值和。若无法满足上述要求，则输出−1。

输入样例

5 6 10

0 2 20 6

2 3 5 6

0 1 2 1

1 1 1 3

1 2 5 4

3 2 10 2

输出样例

17

        （1）编程思路。

        设f[i][j]表示选出的线段铺满数轴上的区间[0,i]且所花费用和不超过j时能收获的最大价值。由于要铺满数轴上的区间[0,L]，也就是背包的第1维得装满，因此初始时除f[0][0]=0外，其余元素均置为-1，f[i][j]=-1时，表示要铺满[0,i]区间不可能。因此，转移是要保证转移前的f[i’][j’]>=0。

        另外，需要对给定线段其放在数轴上的起点从小到大排个序。

         （2）源程序。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int f[1005][1005];
struct Node
{
    int x,y,f,c;
};
int cmp(struct Node a,struct Node b)
{
    return a.x<b.x;
}
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    memset(f,-1,sizeof(f));
    f[0][0]=0;
    int L,n,B;
    scanf("%d%d%d",&L,&n,&B);
    struct Node a[10005];
    int i,j;
    for (i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].f,&a[i].c);
        a[i].y+=a[i].x;
    }
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        for (j=B;j>=a[i].c;j--){
            if(f[a[i].x][j-a[i].c]>=0)
            {
                f[a[i].y][j]=max(f[a[i].y][j],f[a[i].x][j-a[i].c]+a[i].f);
            }
        }
    }
    int ans=-1;
    for (i=1;i<=B;i++)
        ans=max(ans,f[L][i]);
    printf("%d",ans);
    return 0;
}

         将上面的源程序提交给洛谷题库P2854 [USACO06DEC]Cow Roller Coaster S（https://www.luogu.com.cn/problem/P2854），测评结果为“Accepted”。

【例5】宠物小精灵之收服

问题描述

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入

输入数据的第一行包含三个整数：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

样例输入

输入样例

10 100 5

7 10

2 40

2 50

1 20

4 20

输出样例

3 30

           （1）编程思路。

        若收服某个小精灵需要的精灵球的数量超过了小智的精灵球数量或者收服过程中对皮卡丘造成的伤害超过了皮卡丘初始的体力值，则该小精灵不可能被收服。输入时对数据进行预处理，将不可能收服的小精灵忽略掉，只保存可能收服的小精灵。

        设f[i][j]表示扔i个精灵球且皮卡丘损失j体力时所能抓到的最大精灵数。初始值全部为0，用二维费用的0/1背包进行处理。

        最后按皮卡丘损失体力从小到大循环处理数组元素f[n][1]~f[n][m]，找到这些元素中的最大值f[n][i]，此时m-i就是皮卡丘剩余体力的最大值。

        （2）源程序。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int f[1005][505]={0};
int main()
{
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    int num=0;
    int w[102],v[102];
    while (t--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if (x>n || y>=m)       // 不可能收服的小精灵
            continue;
        w[++num]=x;
        v[num]=y;
    }
    int i,j,k;
    for (i=1;i<=num;i++)
        for (j=n;j>=w[i];j--)
            for (k=m-1;k>=v[i];k--)
                f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+1);
    int ans=0;
    for (i=1;i<m;i++)
        if (f[n][i]>f[n][ans]) ans=i;
    printf("%d %d\n",f[n][ans],m-ans);
    return 0;
}

        上面的5个例题中，均是二维费用的0/1背包问题。实际上，若装入背包中的物品可以装入无数次，就是二维费用的完全背包问题了。

【例6】FATE游戏

问题描述

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

输入

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

输出

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

输入样例

10 10 1 10

1 1

10 10 1 9

1 1

9 10 2 10

1 1

2 2

输出样例

0

-1

1

         （1）编程思路。

        由于每种怪都有无数个，而升级需要n经验值，只杀掉s只怪。二维费用的完全背包问题。

        设f[i][j]表示减掉忍耐度i且杀掉j只怪可得到的最大经验值。

        采用二维费用完全背包处理后，若f[m][s]>=n，则可以升级，对数组f按第1维下标（忍耐度）从小到大搜索，若某个f[i][j]>=n，则i值就是可升级时减掉的最小忍耐度，m-i就是还能保留的最大忍耐度；若f[m][s]<n，则无法升级。

        （2）源程序。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int f[105][105];
int main()
{
    int n,m,k,s;
    while (scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
    {
        memset(f,0,sizeof(f));
        int i,j,p;
        for (i=1;i<=k;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            for (j=b;j<=m;j++)       // 忍耐度
            {
                for (p=1;p<=s;p++)   // 个数限制
                {
                    f[j][p]=max(f[j][p],f[j-b][p-1]+a);
                }
            }
        }
        if (f[m][s]>=n)
        {
            for (i=1;i<=m;i++)
            {
                for (j=1;j<=s;j++)
                    if (f[i][j]>=n)
                        break;
                if (j<=s)
                    break;
            }
            printf("%d\n",m-i);
        }
        else
            printf("-1\n");
    }
    return 0;
}

        将上面的源程序提交给HDU OJ题库HDU 2159 FATE（http://acm.hdu.edu.cn/showproblem.php?pid=2159），测评结果为“Accepted”。

         除了上面介绍的二维费用外，有些问题可能涉及更多的费用。比如，有三个方面的费用。

【例7】买年货

问题描述

春节将至，小明要去超市购置年货，于是小明去了自己经常去的都尚超市。

刚到超市，小明就发现超市门口贴了一张通知，内容如下：

值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可免费拿k件商品，凡是购物顾客均有好礼相送。满100元送bla bla bla bla，满200元送bla bla bla bla bla...blablabla....

还没看完通知，小明就高兴的要死，因为他就是都尚的会员啊。迫不及待的小明在超市逛了一圈发现超市里有n件他想要的商品。小明顺便对这n件商品打了分，表示商品的实际价值。小明发现身上带了v1的人民币，会员卡里面有v2的积分。他想知道他最多能买多大价值的商品。

由于小明想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。

输入

输入包含多组测试用例。

每组数据的第一行是四个整数n，v1，v2，k；

然后是n行，每行三个整数a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。

[Technical Specification]

1 <= n <= 100

0 <= v1, v2 <= 100

0 <= k <= 5

0 <= a, b, val <= 100

 

Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。

输出

对于每组数据，输出能买的最大价值。

输入样例

5 1 6 1

4 3 3

0 3 2

2 3 3

3 3 2

1 0 2

4 2 5 0

0 1 0

4 4 1

3 3 4

3 4 4

输出样例

12

4

         （1）编程思路。

        每件商品可以用3种方式获得，用钱买、用积分兑换或者用免费拿的次数免费拿，这样涉及3个方面的费用。设f[i][j][k]表示用i元钱买，用j个积分换，免费拿k件可获得的最大价值，就是一个3维费用的背包问题了，可用4重循环进行处理。

         （2）源程序。

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int f[105][105][6]; // f[i][j][k]表示用i元钱买，用j个积分换，免费拿k件可获得的最大价值
int main()
{
    int a[105],b[105],v[105];
    int n,v1,v2,k;
    while (scanf("%d%d%d%d",&n,&v1,&v2,&k)!=EOF)
    {
        int i,x1,x2,x3;
        for (i=1;i<=n;i++)
            scanf("%d%d%d",&a[i],&b[i],&v[i]);
        memset(f, 0,sizeof(f));
        int ans = 0;
        for (i=1;i<=n;i++)
          for (x1 = v1;x1>=0;x1--)
            for (x2=v2;x2>=0;x2--)
              for (x3=k;x3>=0;x3--)
              {
                    int tmp = 0;
                    if (x1 >=a[i])   // 有钱，用钱买
                        tmp = max(tmp,f[x1-a[i]][x2][x3]+v[i]);
                    if (x2 >=b[i])   // 有积分，用积分兑换
                        tmp=max(tmp,f[x1][x2-b[i]][x3] + v[i]);
                    if (x3>0)        // 可以免费拿，不拿白不拿
                        tmp=max(tmp,f[x1][x2][x3-1]+v[i]);
                    f[x1][x2][x3]=max(f[x1][x2][x3],tmp);
              }
        printf("%d\n",f[v1][v2][k]);
    }
    return 0;
}

        将上面的源程序提交给HDU OJ题库HDU 4501小明系列故事——买年货（http://acm.hdu.edu.cn/showproblem.php?pid=4501），测评结果为“Accepted”。 

练习题

1．P1507 NASA的食物计划（https://www.luogu.com.cn/problem/P1507）

#include <stdio.h>
int main()
{
    int v,m;
    scanf("%d%d",&v,&m);
    int n;
    scanf("%d",&n);
    int a[51],b[51],c[51];
    int f[401][401]={0};
    int i,j,k;
    for (i=1;i<=n;i++)
       scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (i=1;i<=n;i++)
    {
        for(j=v;j>=a[i];j--)
            for (k=m;k>=b[i];k--)
            {
               if (f[j][k]<f[j-a[i]][k-b[i]]+c[i])
                       f[j][k]=f[j-a[i]][k-b[i]]+c[i];
            }
    }
    printf("%d\n",f[v][m]);
    return 0;
}

View Code

#include <stdio.h>
#include <string.h>
struct Node
{
    int sum;        // 停留的总时间
    int ans[101];    // 保存选中的数，其中a[0]是选中的数的个数
};
struct Node f[201][201];
int main()
{
    int m,v,n;
    scanf("%d%d%d",&m,&v,&n);
    int a[101],b[101],c[101];
    int i,j,k,l;
    for (i=1;i<=n;i++)
       scanf("%d%d%d",&a[i],&b[i],&c[i]);
    memset(f,0,sizeof(f));
    for (i=1;i<=n;i++)
       for (j=m;j>=a[i];j--)
          for (k=v;k>=b[i];k--)
          {
              if (f[j-a[i]][k-b[i]].sum+c[i]>f[j][k].sum)
              {
                  f[j][k].sum=f[j-a[i]][k-b[i]].sum+c[i];
                  for (l=1;l<=f[j][k].ans[0];l++)
                      f[j][k].ans[l]=0;
                  f[j][k].ans[0]=f[j-a[i]][k-b[i]].ans[0]+1;
                  for (l=1;l<=f[j-a[i]][k-b[i]].ans[0];l++)
                      f[j][k].ans[l]=f[j-a[i]][k-b[i]].ans[l];
                  f[j][k].ans[f[j][k].ans[0]]=i;   // 选中i
              }
          }
    printf("%d\n",f[m][v].sum);
    for (i=1;i<=f[m][v].ans[0];i++)
        printf("%d ",f[m][v].ans[i]);
    printf("\n");
    return 0;
}