C++ 算法篇 动态规划----背包之六 二维费用背包

二维费用背包

二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为c[i]。

算法
　　费用加了一维，只需状态也加一维即可。设f[i][v][u]表示前i件物品付出两种代价分别为v和u时可获得的最大价值。
　　状态转移方程就是：f [i][v][u]  =  max {  f [i-1] [v] [u]   , f [i-1] [v-a[i]] [u-b[i]]  + c[i] }。如前述方法，可以只使用二维的数组：当每件物品只可以取一次时变量v和u采用逆序的循环，当物品有如完全背包问题时采用顺序的循环。当物品有如多重背包问题时拆分物品。

物品总个数的限制
　　有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取M件物品。这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为1，可以付出的最大件数费用为M。换句话说，设f[v][m]表示付出费用v、最多选m件时可得到的最大价值，则根据物品的类型（01、完全、多重）用不同的方法循环更新，最后在f[0..V][0..M]范围内寻找答案。
另外，如果要求“恰取M件物品”，则在f[0..V][M]范围内寻找答案。

【例】潜水员

【问题描述】
 潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
   例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：
    3 36 120
    10 25 129
    5 50 250
    1 45 130
    4 20 119
   如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。
   你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。
【输入格式】
 第一行有2整数m,n（1<=m<=21,1<=n<=79）。它们表示氧，氮各自需要的量。
  第二行为整数k（1<=n<=1000）表示气缸的个数。
 此后的k行，每行包括ai，bi，ci（1<=ai<=21，1<=bi<=79，1<=ci<=800）3整数。这些各自是：第i个气缸里的氧和氮的容量及汽缸重量。
【输出格式】
  仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

样例输入：

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

样例输出：
249

问题分析：
这道题的分法与之前的背包问题不同。前面的背包问题，都是限制着费用的增加，问“最大价值”是什么。这题的问法是相反的，处理方式就需要相反。

问题一的例解程序，同样的输入样例，输出是250（最大值），供参考：

#include "bits/stdc++.h"
using namespace std;
int v, u, k;
int a[1001], b[1001], c[1001];
int f[101][101];
int main()
{  f[0][0] = 0;
   scanf("%d%d%d",&v,&u,&k);// m,n,k;
   for (int i = 1; i <= k; i++)    scanf("%d%d%d",&a[i],&b[i],&c[i]);
   for (int i = 1; i <= k; i++)
     for (int j = v; j >=a[i]; j--)//01背包
       for (int l = u; l >=b[i]; l--)//多了一重限制条件的01背包；
        f[j][l] = max (f[j][l] , f[j-a[i]][l-b[i]] + c[i]) ;
   printf("%d",f[v][u]);
   return 0;
}

现在是问题二:也就是潜水员本题的问法。此时问的是必须完全满足费用条件后，成本最低(答案就是249)，它与前一问法是反过来的（所以是最大值250）。如果换到01背包的例题中，可以修改成这个样子：
旅行者至少需要m升燃料完成旅程，现有n个品种包装，每种是ai升和bi元，若每种只能选一，请问如何让费用最低？（01）若每种可以选N，费用最低又是多少？（完全）
【样例输入】

10 4
2 1
3 3
4 5
7 9

【样例输出】

０１背包答案仍然是12

#include "bits/stdc++.h"
using namespace std;
const int maxm = 2001, maxn = 31;
int m, n;
int w, c;
int f[maxm];
int main()
{  scanf("%d%d",&m, &n);   //背包容量m和物品数量n
   memset(f,127,sizeof(f));//注意要反过来求，需要全部赋一个很大的对照值；
   f[0]=0;                 //初值仍然是0;
   for (int i=1; i <= n; i++)
   {  scanf("%d%d",&w,&c);
      for (int j =m; j >= 0; j--)
      { int t=j+w;        //这样枚举出小于m的所有可能
        if(t > m) t=m;    //超出的需求扔了，
        if (f[t] > f[j]+c) f[t] = f[j]+c;//单纯选出费用的最小值；
      }
    }
    printf("%d",f[m]);    // f(m)为最优解
    return 0;
}

完全背包答案应是５

#include "bits/stdc++.h"
using namespace std;
const int maxm = 2001, maxn = 31;
int m, n;
int w, c;
int f[maxm];
int main()
{  scanf("%d%d",&m, &n);   //背包容量m和物品数量n
   memset(f,127,sizeof(f));//注意要反过来求，需要全部赋一个很大的对照值；
   f[0]=0;                 //初值仍然是0;
   for (int i=1; i <= n; i++)
   {  scanf("%d%d",&w,&c);
      for (int j =0; j <= m; j++)
      { int t=j+w;        //这样枚举出小于m的所有可能
        if(t > m) t=m;    //超出的需求扔了，
        if (f[t] > f[j]+c) f[t] = f[j]+c;//单纯选出费用的最小值；
      }
    }
    printf("%d",f[m]);    // f(m)为最优解
    return 0;
}

有了上面01背包和两维程序变形的铺垫，下面是潜水员程序的题解，就容易理解了。
【参考程序】

#include "bits/stdc++.h"
using namespace std;
int v, u, k;
int a[1001], b[1001], c[1001];
int f[101][101];
int main()
{  memset(f,127,sizeof(f));  //初始化为一个很大的正整数
   f[0][0] = 0;
   scanf("%d%d%d",&v,&u,&k);// m,n,k;
    for (int i = 1; i <= k; i++)     scanf("%d%d%d",&a[i],&b[i],&c[i]);
    for (int i = 1; i <= k; i++)
     for (int j = v; j >= 0; j--)//０１背包
       for (int l = u; l >= 0; l--)  //多了一重限制条件的０１背包；
       {  int t1 = j+ a[i],t2 = l + b[i];
          if (t1 > v)  t1 = v; //若氮、氧含量超过需求，可直接用需求量代换，
          if (t2> u)  t2 = u; //不影响最优解
          f[t1][t2] = min (f[t1][t2] , f[j][l] + c[i])  ;
       }
   printf("%d",f[v][u]);
   return 0;
}

小结

       事实上，当发现由熟悉的动态规划题目变形得来的题目时，在原来的状态中加一维以满足新的限制是一种比较通用的方法。希望你能从本讲中初步体会到这种方法。

1、L国的战斗之间谍（二维背包）

题目背景：L国即将与I国发动战争！！

题目描述：
俗话说的好：“知己知彼，百战不殆”。L国的指挥官想派出间谍前往I国，于是，选人工作就落到了你身上。

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

输入格式
N M X

A1 B1 C1

A2 B2 C2

………………

AN BN CN

输出格式
能得到的资料总数

输入输出样例
输入 

3 10 12
10 1 11
1 9 1
7 10 12

输出 
11
说明/提示
数据范围：

1≤n≤100,1≤m≤1000, 1≤x≤1000