动态规划——背包问题

2020年06月05日 阅读数:34
这篇文章主要向大家介绍动态规划——背包问题,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

  今天开始进入了动态规划的专题学习。html

  动态规划(dynamic programming),是运筹学的一个分支,其主要用于寻找最优方案。说到最优方案,咱们不由要将其与一种最基本的算法——贪心算法,联系起来。事实上,正是因为这种共性,使得不少问题有着多解性。node

  百度百科中有着这样一句话:“20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。”这其实也就点出了动态规划的精髓所在——多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。而落实到具体解决问题的过程当中,其实就是寻求状态转移方程的过程。ios

 

  上面先从总体上来概述了一下动态规划的思想,下面咱们经过算法世界里经典的背包问题来具体的体会这种思想。算法

  首先咱们先对背包问题有一个概述,有n个物品,第i个物体的重量是w[i],价值是v[i],在给定承重为m的背包中,放入物体,求解全部的方案中,物体总价值最大的那一种。这即是最原始的背包问题,而基于选择物品的种种限制条件不一样,背包问题又能够分为不少类型,这里暂时不一一列举,咱们会在后面的文章中分析到。编程

 

  01背包问题。api

  在这个问题中,对于每一个物体,只容许存在两个状态:不装入背包或者仅仅装入1个,从这里其实也可以理解01背包这个名称的由来,由于物体只对应这0或1这2种状态。数组

  下面咱们开始分解决策过程以寻求各阶段之间的关系并获得状态转移方程。咱们从决策的过程当中开始分析,假设咱们当前正在选择第i个物品,那么咱们决策的结果有以下两种状况。安全

  ①将第i个物品装入背包当中。数据结构

  ②不将第i个物品装入背包当中。less

  针对①状况,咱们必须基于前i-1件物品装入背包当中的方案是最优的,若是咱们用数组dp[i]表示装入背包i件物品最大的价值,这就找到了先后两个阶段之间的关系,那么针对①状况,dp[i] = dp[i - 1] + w[i]。

  针对状况②,显然有dp[i] = dp[i - 1]。

  那么dp[i],到底应给等于多少呢?咱们要找的是价值最大的方案嘛,显然dp[i] = max(dp[i-1] , dp[i-1] + v[i])。

  可能有人会问了,max(dp[i-1] , dp[i-1] + w[i])显然等于dp[i - 1] + w[i]啊,那这个方程还有什么意义?

  别急,咱们还有另一个重要因素——重量,没有考虑。咱们设j为当前方案下的背包的容量,那么此时dp[i][j]就表示把i件物体装入容量为j的空间中能够获得的最大价值数。

  针对①,有dp[i][j] = dp[i][j-w[i]] + v[i],这里至关于在大的背包(容量为j)里面套了一个小的背包(容量为j - w[i]),这样一来,分阶段之间的重量关系也创建起来了。 一样。

  针对②,有dp[i][j] = dp[i-1][j]。

  综合来看,即dp[i][j] = max(dp[i-1][j] ,  dp[i][j-w[i]] + v[i])。有个该状态转移方程,咱们就能够从第一件物品开始依次选择,最终获得最优方案。

  咱们经过一个具体的题目体会一下这个模型的应用。(Problem source : hdu 2602)

 

Problem Description
Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
 
 
Input
The first line contain a integer T , the number of cases. Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
 
Output
One integer per line representing the maximum of the total value (this number will be less than 2 31).
 
  题目大意:标准的01背包问题。
  编程实现:基于咱们讨论的状态转移方程,咱们首先枚举这n个物体,这与上文中咱们分析问题的过程是相呼应的。假设枚举到第i个物体,咱们要抉择选仍是不选,此时咱们再枚举此时的背包空间,并利用状态转移方程记录下当前最优的方案,这里其实也是上文中咱们提到的构造“小背包”的过程。
  参考代码以下。
 
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn = 1010;
const int minn = -999999;

int dp[maxn][maxn];
int n, m;
int w[maxn],v[maxn];

int main()
{
      int t;
      scanf("%d",&t);
      while(t--)
      {
            memset(dp,0,sizeof(dp));
            memset(w,0,sizeof(w));
            memset(v,0,sizeof(v));
            scanf("%d%d",&n,&m);
            for(int i = 1;i <= n;i++)
                  scanf("%d",&w[i]);
            for(int i = 1;i <= n;i++)
                   scanf("%d",&v[i]);
       for(int i = 1;i <= n;i++)
       {
            for(int j = m;j >= 0;j--)
            {
                  if(j - v[i] >= 0)
                      dp[i][j] = max(dp[i-1][j] , dp[i-1][j-v[i]] + w[i]);
                  else
                      dp[i][j] = dp[i-1][j];
            }
       }
       printf("%d\n",dp[n][m]);
      }
      return 0;
}

 

    总结一下,用动态规划求解最优方案的时候,咱们要分析出分阶段之间的联系,而后利用这个联系,不断实现局部最优,而后一步一步引导出总体最优。而分阶段之间的联系,本质上就是一种递推关系,因此动态规划其实仍是算法世界里最基本的递推思想的应用。学过生成函数的读者可能会注意到,这个过程其实与构造生成函数很类似,其实能够说生成函数虽然解决组合数学的问题,却的确用动态规划来编程实现的,可见动态规划的方法在算法世界中的重要地位。

 

  经过上文对01背包问题的介绍,这里咱们再来讨论一种01背包的变种问题。(Problem source : hdu 2546)

Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计,即在购买以前判断余额。若是购买一个商品以前,卡上的剩余金额大于或等于5元,就必定能够购买成功(即便购买后卡上余额为负),不然没法购买(即便金额足够)。因此你们都但愿尽可能使卡上的余额最少。 某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可以使卡上的余额为多少。
 
Input
多组数据。对于每组数据: 第一行为正整数n,表示菜的数量。n<=1000。 第二行包括n个正整数,表示每种菜的价格。价格不超过50。 第三行包括一个正整数m,表示卡上的余额。m<=1000。
n=0表示数据结束。
 
Output
对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。


  数理分析:经过读题后,发现这个问题没法与咱们上文给出的模型彻底对应起来,由于,在这个问题中,显然要把每一种菜当作01背包模型中的物体,可是在这里好像只给出了“价值”和“占用空间”中的一个量,那显然这个问题也就变得有些不一样了,咱们也就不能盲目的调用上题中的代码了。
  咱们思考另一个模型:给定n种物体各自占用的空间,和一个容量为v的背包,要求每种物体只能在背包中放一个(每一个物体就只有两种状态了),那么我怎样安排这n种物体,使 其尽量的填满背包呢?
  咱们将这个模型和这个问题进行比较,显然是匹配的,所以咱们接下来要作的就是解决这个新的01背包模型。
  咱们设置数组dp[v'],来表示容积为v'的背包容纳物体的最大致积。相似于上文中咱们的分析过程,咱们遍历全部的物体来求得最优解,假设当前选择第i种物体,其体积是v[i],当前的背包体积大小是v'。则以后的决策分为两种状况:
  ①不装入第i种物体,则此时dp[v'] = dp[v']。
  ②装入第i中物体,则此时dp[v'] = dp[v' - v[i]] + v[i]。
  由此咱们不可贵到整个决策过程的状态转移方程:
                            dp[v'] = max(dp[v'],dp[v' -price[i]] + price[i])
  基于对这个模型的分析,对上面的问题也就不难求解了。
  参考代码以下。
 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
const int N = 1100;
using namespace std;

int price[N];
int dp[N];

int n , money;
void ZeroOnePack(int price)
{
     for(int i = money;i - price >= 0;i--)
     {
            dp[i] = max(dp[i - price]  + price ,  dp[i]);
     }
}

int main()
{

    while(scanf("%d",&n) != EOF && n)
    {
          for(int i = 0;i < n;i++)
              scanf("%d",&price[i]);
        sort(price , price + n);
        memset(dp , 0 , sizeof(dp));
          scanf("%d",&money);
          if(money < 5)
          {
               printf("%d\n",money);
               continue;
          }
          money -= 5;
          for(int i = 0;i < n - 1;i++)
                ZeroOnePack(price[i]);
          printf("%d\n",money - dp[money]+ 5 -price[n-1]);


    }
}

  经过上面两个01背包问题咱们不难发现利用动态规划思想解决问题的特色,能够说须要给程序语言中的数据类型赋予丰富的现实含义,并且要必须时刻清晰的记住这些数据结构表明着什么。例如上文中一开始对数组dp[i]中i表明什么,dp[i]又表明什么的阐释,它们的含义在不一样的问题中会有这不一样的解释,这也是动态规划类问题呈现出灵活性极大的缘由。
  基于对数据类型内涵的理解,下一步则体现了动态规划思想的精髓——寻求状态转移方程,咱们将整个大的过程“肢解”成小的过程,寻求每一个小状态之间均知足的联系,便可一步一步从初始状态转移到终态求得最优解。
  以上是关于动态规划类问题一个小小的总结,更多的实践分析,文章的后面将会继续给出。

 

  基于咱们对最标准的01背包模型的介绍,下面咱们将会给出一些在此模型基础上创建起来的变种问题。对于彻底背包等基本模型,咱们也会采起相同的策略。
  那么下面咱们来看一个01背包的变种问题。(Problem source : hdu 3466)
 

Problem Description
Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more. The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi. If he had M units of money, what’s the maximum value iSea could get?
 
Input
There are several test cases in the input.
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money. Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.
 
Output
For each test case, output one integer, indicating maximum value iSea could get.


  题目大意:给出n种物体中每种物体的三个参量:P、Q、V分别表明价格、购买该物品时手中至少有的钱数以及价值数,那么请你求解用m元如何可以买到最大价值的物体。
  数理分析:整体来看,是典型的01背包问题,只不过在这个变种问题中,选择每种物体的时候增长了限制条件。
  首先咱们按照01背包的思路对问题进行初步的分析,咱们设置一维数组dp[j]来表示花费j元是的最优方案。那么咱们能够由以下的状态转移方程进行求解。
   for i  (1 to n)
       for j  (m to Q[i])
              dp[j] = max(dp[j] , dp[j-P[i]] + V[i])
  根据状态转移方程,咱们容易看到,dp[j]的求解是要基于dp[j-P[i]]的,而j的最小值是Q[i],也就是说,dp[j]的正确求解是要基于dp[Q[i]-P[i]]的。
  咱们发现,若是在选择第i-1种物体的时候,Q[i-1] - P[i-1] < Q[i] - P[i],则这个过程当中会更新一次dp[Q[i] - P[i]],而若是Q[i-1] - P[i-1] > Q[i] - P[i],则不会更新。这显然会致使dp[Q[i] - P[i]]缺失了状态,所以后面的求解过程也就都错了。咱们找到了递推关系,所以咱们对于n种物体的决策,要先按照Q[i] - P[i]进行递增排序,而后从第一个物体开始求解。
  参考代码以下。

 

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

struct node
{
     int p , q , v;
};
node a[505];
int dp[5005];
bool cmp(node a , node b)
{
      return a.q-a.p < b.q-b.p;
}
int main()
{
        int n , m;
        while(scanf("%d%d",&n,&m) != EOF)
        {
              memset(dp , 0 , sizeof(dp));
              for(int i  =1 ;i <= n;i++)
                  scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
              sort(a + 1 , a + n + 1 , cmp);
            for(int i = 1;i<= n;i++)
                  for(int j = m;j >= a[i].q;j--)
                        dp[j] = max(dp[j] , dp[j-a[i].p] + a[i].v);

                        printf("%d\n",dp[m]);
        }
}

 

  咱们不妨再来看一个关于01背包的变种问题。(Problem source : hdu2955)
  

Problem Description
The aspiring Roy the Robber has seen a lot of American movies, and knows that the bad guys usually gets caught in the end, often because they become too greedy. He has decided to work in the lucrative business of bank robbery only for a short while, before retiring to a comfortable job at a university.
 
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
 
Input
The first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj . Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .


  题目大意:给出参量P表示小偷被抓的几率,而后给出n家银行有的财产val[]和被抓几率cost[],求解一个小偷偷窃过程当中不超过这个被抓几率可以偷取的最大价值数。
  数理分析:咱们经过将这个问题与标准的01背包问题进行比较发现,这里每家银行的财产是01背包问题中的物品的价值val,而这里的被抓几率其实就是01背包问题中每种物体的重量,本质上能够说是一种费用——cost。
  那么咱们对比01背包中惯用的思路,是设置dp[i]数组用来记录容量为i的背包装入的最大价值数。也就是说,物体的费用是dp数组的下标,而dp[]储存的值表示价值的最大数。而在这个问题中咱们注意到,费用是几率,也就是说出现了小数,那么显然其没法做为dp[]的下标了。所以咱们这里须要灵活的转化一下思路,设置dp[i]表示偷取价值为i时所须要冒得最小风险,即被抓的几率最小。
  咱们将问题再进一步转化,题设给出的是“被抓几率”,咱们不难经过几率的相关性质求出其“安全几率”。(由于这个过程只要出现一次被抓就被视为被抓,而安全状态自必须知足每次抢劫银行都安全,所以对于安全状态的几率分析能够用到分步的乘法定理,这是利于咱们找到各个状态之间的转移关系的。)咱们对整个决策过程两个参量val和cost的相关关系作一个简单的分析,随着val的增大,cost必将减少,容易找出临界状态从dp[]的末端开始扫,dp[i]恰好大于小偷的安全几率1-P时,此时的i即是小偷安全状态下可以偷取的最大财物。
  基于上文对该问题在典型的01背包如何变种的分析,咱们只需用动态规划的思想计算出dp[]数组便可。模拟01背包中的过程,咱们不难想出以下的状态转移方程。
  for i  1 to n
        for j  ∑cost[] to 0
                 dp[j] = max(dp[j] , dp[j-val[i]]*cost[i])
  参考代码以下。

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxv = 10001;
const int maxn = 101;

double cost[maxn] , dp[maxv];
int val[maxn];
int main()
{
      int t , n , sumv;
      double P;
      scanf("%d",&t);
      while(t--)
      {
            sumv = 0;
          scanf("%lf %d",&P,&n);
          P = 1 - P;
          for(int i = 1;i <=n;i++)
          {
                 scanf("%d %lf",&val[i],&cost[i]);
                 cost[i] = 1 - cost[i];
                 sumv += val[i];
          }
          dp[0] = 1;
          for(int i = 1;i <= sumv;i++)
               dp[i] = 0;
          for(int i = 1;i <= n;i++)
          {
                for(int j = sumv;j >= val[i];j--)
                      dp[j] = max(dp[j] , dp[j-val[i]]*cost[i]);
          }
          for(int i = sumv;i >= 0;i--)
          {
                if(dp[i] -P > 0.000000001)
                {
                     printf("%d\n",i);
                     break;
                }
          }
      }
}

   咱们再来看一道基于01背包的变种问题。(Problem source : hdu 1203)
Problem Description

Speakless很早就想出国,如今他已经考完了全部须要的考试,准备了全部要准备的材料,因而,便须要去申请学校了。要申请国外的任何大学,你都要交纳必定的申请费用,这但是很惊人的。Speakless没有多少钱,总共只攒了n万美圆。他将在m个学校中选择若干的(固然要在他的经济承受范围内)。每一个学校都有不一样的申请费用a(万美圆),而且Speakless估计了他获得这个学校offer的可能性b。不一样学校之间是否获得offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他能够收到至少一份offer的最大几率。(若是Speakless选择了多个学校,获得任意一个学校的offer均可以)。
 
Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的几率。
输入的最后有两个0。
 
Output
每组数据都对应一个输出,表示Speakless可能获得至少一份offer的最大几率。用百分数表示,精确到小数点后一位。


  梳理一下该题的数据咱们不难发现,n个学校,每一个学校有两个参量,分别是费用参量cost[]以及咱们要求解的最优的指标参量val[],而且容易看出对于每一个学校咱们只能有两种状态,所以就不难将其与典型的01背包问题联系起来了。
  另外值得注意的一点是,本题须要求解被录取的最大几率,而被录取事件只要有一所学校录取便可,结合必定的几率的知识,咱们很容易想到求它的反面,即最小的没被录取的几率。
  而对最小没被录取几率的求解,即可模拟相似01背包的求解过程了,咱们设置dp[j]记录费用为j时没被录取的最小几率,假设咱们当前正在决策第i个学校,基于对该学校投或不投这两种状况:
  若是选择该校,有dp[j] = dp[j - cost[i]]*val[i]。
  若是不选择该校,dp[j] = dp[j]。
  而到底选不选该校,经过以下的状态转移方程便可。
  dp[j] = min(dp[j] , dp[j-cost[i]]*val[i])。
  参考代码以下。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10000 + 5;

int main()
{
      double dp[maxn];
      double val[maxn];
      int cost[maxn];
      int n , m;
      while(scanf("%d %d",&n,&m) != EOF)
      {
          if(n == 0 && m == 0)  break;
          for(int i = 0;i <= n;i++)
              dp[i] = 1.0;
           for(int i = 1;i <= m;i++)
            {
               scanf("%d%lf",&cost[i],&val[i]);
                val[i] = 1 - val[i];
            }
           for(int i = 1;i <= m;i++)
           {
                 for(int j = n;j >= cost[i];j--)
                       dp[j] = min(dp[j] , dp[j-cost[i]]*val[i]);
           }

          printf("%.1lf%%\n",(1-dp[n])*100);

      }
      return 0;

}

 


  经过这道问题咱们也能够更进一步理解01背包这一模型,只要是对n个只有两种状态且含有两个参量(一个是费用参量,一个是最优指标)的物体的最优决策过程,咱们均可以将其看作01背包问题的变种。    

  今天介绍背包问题中第二个模型——彻底背包问题。

  仍是基于上文中01背包的条件,不过对于每一个物体再也不是两种状态,而是能够装入任意个,这种背包问题便是彻底背包问题。

  尽管咱们讨论过的01背包问题与彻底背包问题很相似,可是在分析上却有着明显的差别。

  回想起咱们在01背包问题的模型中,设置二维数组dp[i][j],前i个物体装入容积为j的背包中,可是因为彻底背包问题对物体数目不设限的特色,所以j出现的状况就太多了。

  举个例子,在01背包问题中,第一个物体v[1] = 1 , w[1] = 1 , 背包容积是m,dp[1][1] = 1,然根据这个条件和状态转移方程求得最优解。而若是在彻底背包中,则会出现dp[1][1] = 1 , dp[1][2] = 2 , dp[1][3] = 3,……dp[1][m] = m,这就形成初始条件太多,再利用状态转移方程求解,就使得求解过程太过冗长。

  为了不引发上述求解过程变得繁琐,咱们直接设置dp[j]记录容积为j的背包装入物体的最大价值并经过穷举背包的容积j(j <= w_of_big),以此来枚举每一个物体须要拿几个的状况,以简化求解过程。

  咱们设dp[j]记录容积为j的背包装入物体的最大价值,v[i]表示其价值,w[i]表示其体积。咱们依然从过程开始分析,假设咱们当前在选取第i种物体,则有k(k = w_of_big / w[i])种状况,即选0、一、2……k个物体。咱们设置参数j∈[w[i],w_of_big]并依次遍历这个区间的数(之因此这样设置在上文中已有所讨论),此时咱们暂且认为该物体只有两种状态0、1,那么经过01背包的模型,咱们会获得状态方程dp[j] = max(dp[j] , dp[j - w[i]] + v[i]),可是随着j的增长,在dp[j-w[i]]这种状态下的方案中其实已经存在了选取了一些数量的该物体,这也就实现了该种物体不限数装入背包的限制条件。

  咱们再来经过一个具体的问题来应用一下这个模型。(Problem source : hud 1114)  

Problem Description
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
 
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it's weight in grams.
 
Output
Print exactly one line of output for each test case. The line must contain the sentence "The minimum amount of money in the piggy-bank is X." where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line "This is impossible.".

  题目大意:给出一个储钱罐空载时和满载时的容量,而后给你n种钱币的价值和重量,须要你求解装满储钱罐状况下钱币总价值最小的方案。

  数理分析:很典型的彻底背包问题了,与上面的模型有点区别的是,这里求的是最小值。那么在状态转移方程的求解和dp数组的初始化上就须要有所改动。

  参考代码以下。

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define INF 0xfffffff
using namespace std;
int dp[10010];

int main()
{
      int E , F ;
      int  ncase;
      int  v , w ;
      int  i , j ;
      int kind_of_coin;
      int v_of_pig;
      scanf("%d",&ncase);
      while(ncase--)
      {
           scanf("%d%d",&E,&F);
           v_of_pig  =F - E;
           scanf("%d",&kind_of_coin);
           for(i = 0;i <= v_of_pig;i++)
                  dp[i] = INF;
            dp[0] = 0;
          for(i = 1;i <= kind_of_coin;i++)
          {
               scanf("%d%d",&v,&w);
                 for(j = w;j <= v_of_pig;j++)
                 {
                     dp[j] = min(dp[j],dp[j-w]+v);
                 }

          }
         if(dp[v_of_pig] == INF)
              printf("This is impossible.\n");
         else
              printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v_of_pig]);
      }
}

  咱们再来看一道有关彻底背包模型的问题。(Problem source : hdu 4508)
  

Problem Description
  对于吃货来讲,过年最幸福的事就是吃了,没有之一!   可是对于女生来讲,卡路里(热量)是天敌啊!   资深美女湫湫深谙“胖来如山倒,胖去如抽丝”的道理,因此她但愿你能帮忙制定一个食谱,能使她吃得开心的同时,不会制造太多的天敌。
  固然,为了方便你制做食谱,湫湫给了你每日食物清单,上面描述了当天她想吃的每种食物能带给她的幸福程度,以及会增长的卡路里量。
 
Input
  输入包含多组测试用例。   每组数据以一个整数n开始,表示天天的食物清单有n种食物。
  接下来n行,每行两个整数a和b,其中a表示这种食物能够带给湫湫的幸福值(数值越大,越幸福),b表示湫湫吃这种食物会吸取的卡路里量。   最后是一个整数m,表示湫湫一天吸取的卡路里不能超过m。
   [Technical Specification]   1. 1 <= n <= 100   2. 0 <= a,b <= 100000   3. 1 <= m <= 100000


  经过读题不难看出题设对于每种食物拿取的量并无限制,而每种食物的能量即为背包问题中每种物体的费用,而幸福值显然是每种物体的价值,进行这一步转化,咱们即可以肯定这是一个最原始的彻底背包问题了。
  参考代码以下。

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int N = 110;
using namespace std;
int n , m;

struct Food
{
     int val;
     int cost;

}f[N];

int dp[100005];

void CompletePack(int cost , int val)
{
    for(int i = cost;i <= m;i++)
        dp[i] = max(dp[i] , dp[i-cost] + val);
}
int main()
{


    while(scanf("%d",&n) != EOF)
    {

         memset(dp , 0 , sizeof(dp));
         for(int i = 1; i <= n;i++)
              scanf("%d%d",&f[i].val,&f[i].cost);

         scanf("%d",&m);
         for(int i = 1;i <= n;i++)
               CompletePack(f[i].cost , f[i].val);

           printf("%d\n",dp[m]);
    }


}

 

    让咱们再看一道彻底背包的变种题。(hdu 3008)
  

Problem Description
Have you ever played the Warcraft?It doesn't matter whether you have played it !We will give you such an experience.There are so many Heroes in it,but you could only choose one of them.Each Hero has his own skills.When such a Skill is used ,it costs some MagicValue,but hurts the Boss at the same time.Using the skills needs intellegence,one should hurt the enemy to the most when using certain MagicValue.
Now we send you to complete such a duty to kill the Boss(So cool~~).To simplify the problem:you can assume the LifeValue of the monster is 100, your LifeValue is 100,but you have also a 100 MagicValue!You can choose to use the ordinary Attack(which doesn't cost MagicValue),or a certain skill(in condition that you own this skill and the MagicValue you have at that time is no less than the skill costs),there is no free lunch so that you should pay certain MagicValue after you use one skill!But we are good enough to offer you a "ResumingCirclet"(with which you can resume the MagicValue each seconds),But you can't own more than 100 MagicValue and resuming MagicValue is always after you attack.The Boss is cruel , be careful!
 
Input
There are several test cases,intergers n ,t and q (0<n<=100,1<=t<=5,q>0) in the first line which mean you own n kinds of skills ,and the "ResumingCirclet" helps you resume t points of MagicValue per second and q is of course the hurt points of LifeValue the Boss attack you each time(we assume when fighting in a second the attack you show is before the Boss).Then n lines follow,each has 2 intergers ai and bi(0<ai,bi<=100).which means using i skill costs you ai MagicValue and costs the Boss bi LifeValue.The last case is n=t=q=0.
 
Output
Output an interger min (the minimun time you need to kill the Boss)in one line .But if you die(the LifeValue is no more than 0) ,output "My god"!


  题目大意:英雄和boss的血量均为100,给出英雄n个技能的伤害以及耗蓝度,进行回合制做战。boss每回合的伤害均为q,而英雄每回合后回蓝为定值t,那么求解英雄杀死boss的最小回合数。
  数理分析:容易看到,对于每种状态中,咱们有一个限制参数——蓝条,而咱们的最优指标是最大的伤害,这其实对应着背包中的cost[]和val[],而显然每种技能是使用次数是不限的(只要蓝够用),所以这与彻底背包的模型很是相似。
  可是相对于经典的彻底背包问题,这个问题中的多了一重记录回合数参数。咱们先来完成子问题化,对于每种状态,显而易见的是回合数i和当前剩余的蓝条,即咱们设置dp[i][j]记录第i回合结束后英雄蓝条剩余量为j时形成的最大伤害。
  下面咱们该找寻状态转移方程了。咱们模拟一下动态规划求解的过程dp[i][j]的过程。
  首先咱们须要明确的是咱们须要找到它与dp[i-1][j]有着怎样的关系,那么基于dp[i-1][j],第i-1回合结束后,当前的蓝条显然会发生变化(回蓝和技能耗蓝)。即基于子问题dp[i-1][j]记录最优解,假设第i回合使用了第k个技能,当前的状态应该表示成dp[i][j+t-cost[k]]。
  对于子问题dp[i-1][j]记录的最优解,咱们在遍历n种能够释放的技能,并维护最优解,则将完成第i回合全部子问题的最优解的计算。
  即if(j >= cost[k]) => dp[i][j+t-cost[k]] = max(dp[i][j+t-cost[k]] , dp[i-1][j] + val[k])  k∈[1,n]。
  这个过程综合起来,可用下面的伪码来表达。
  for i 1 to 100/q
      for j 0 to 100
          for k 1 to n
     if(j >= cost[k])
    dp[i][j+t-cost[k]] = max(dp[i][j+t-cost[k]] , dp[i-1][j] + val[k])
  一旦dp[i][j] >= 100,则代表此时英雄已经杀死boss(第一层循环i的取值即保证在循环内英雄是活着的)。
  参考代码以下。
 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 110;
int dp[N][N] , cost[N],val[N];

int main()
{
     int n , t , q;
     while(scanf("%d%d%d",&n,&t,&q) != EOF && n + t + q)
     {
          cost[0] = 0 , val[0] = 1;//普攻
           for(int i = 1;i <= n;i++)
              scanf("%d%d",&cost[i],&val[i]);

           for(int i = 0;i < N;i++)
               for(int j = 0;j < N;j++)
                  dp[i][j] = -9999999;

           dp[0][100] = 0;
             try
             {
                    for(int i = 1;(i-1)*q < 100;i++)
                          for(int j = 0;j <= 100;j++)
                             for(int k = 0;k <= n;k++)
                                if(j >= cost[k])
                    {
                         int temp = min(100 , j + t - cost[k]);//蓝条有上限
                         dp[i][temp] = max(dp[i][temp] , dp[i-1][j] + val[k]);
                            if(dp[i][temp] >= 100)
                                   throw i;
                    }
                    printf("My god\n");
             }
             catch(int ans)
             {
                  printf("%d\n",ans);
             }
     }
}

 

  基于对01背包和彻底背包的学习,咱们下面来看多重背包的模型。
  多重背包其实仍是基于01背包和彻底背包的情景,不过在多重背包中会再给出一个数组number[],用来记录n种物体中每种物体最多能够取的数量。
  基于咱们对在上面两个模型中对动态规划思想的初探,在这里寻找状态转移方程就显得轻车熟路了,咱们设置数组dp[i][j]表示取了i种物体,装容量为j的背包的最大价值数,那么咱们容易获得以下的状态转移方程:
    dp[i][j] = max{dp[i-1][j-k*value[i]] + k*value | k∈[0,number[i]]}
  可是在实际的编程中,为了简化程序,咱们须要对该状态转移方程进行简化处理。联系咱们已经学过的两个简单的背包模型,咱们但愿用这两个简单模型的巧妙组合来简化多重背包的编程实现。
  对于第i种物体,若是number[i] * weight[i] > Pack_weight,那么容易看到,此时对于第i种物体的选择策略,是与彻底背包相同的。
  而对于第i中物体,若是不知足上面的不等式,那么咱们经过二进制的思想巧妙的将其转化成01背包问题,咱们固然能够把每一个物体当作一个01物体来处理,可是这里介绍一个基于二进制数的优化方法。

  咱们将第i种物品的数量number[i]视做一个二进制数并将其转化成二进制数的形式,即number[i] = 2^0 + 2^1 + 2^2……+2^m + (number[i] - ∑2^i)(i∈[1,m]),咱们如今将这m+1组数看作m+1个01物体。首先,这m+1组物体的全部组合状况显然是包含了当前种类物体选取的全部状况。其次,相对于将每一个物体看作01物体进行决策,这种基于二进制的分组然后进行01决策显然简化了计算量。
  在咱们介绍01背包问题模型的时候,为了方便理解,咱们设置了二维数组dp[][],实际上,能够经过简单的优化来下降dp数组的维度,由于根据上文的分析,多重背包中既须要01背包模型,也须要彻底背包模型,所以它们的dp数组的含义应该是相同的。
  咱们设置数组dp[i]来表示容积为i的背包盛放物体的最大价值数。
  对于彻底背包来说,基于该种物体能够无限的取,因此咱们在遍历容积的时候,显然是从小容积背包往大容积背包扫,这样既可表示该种物体拿了多个。
  而对于01背包来说,因为该物体只能出现0和1两种状态,因此遍历容积i的时候,须要从大容积背包往小容积背包扫,这样实现该物体至多被装入一次的限制条件。
 
  基于上文的分析,咱们经过具体的问题来编程实现多重背包的模型。(Problem source : hdu 2191)
  

Problem Description
急!灾区的食物依然短缺! 为了挽救灾区同胞的生命,心系灾区同胞的你准备本身采购一些粮食支援灾区,如今假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,而且只能整袋购买。 请问:你用有限的资金最多能采购多少公斤粮食呢?
后记: 人生是一个充满了变数的生命过程,天灾、人祸、病痛是咱们生命历程中不可预知的威胁。 月有阴晴圆缺,人有旦夕祸福,将来对于咱们而言是一个未知数。那么,咱们要作的就应该是珍惜如今,感恩生活—— 感谢父母,他们给予咱们生命,抚养咱们成人; 感谢老师,他们授给咱们知识,教咱们作人 感谢朋友,他们让咱们感觉到世界的温暖; 感谢对手,他们令咱们不断进取、努力。 一样,咱们也要感谢痛苦与艰辛带给咱们的财富~
 
Input
输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,而后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
 
Output
对于每组测试数据,请输出可以购买大米的最多重量,你能够假设经费买不光全部的大米,而且经费你能够不用完。每一个实例的输出占一行。


  题目大意:很明显的多重背包问题。
  数理分析:详细的分析在上文中已经呈现,这里便再也不赘述。
  参考代码以下。

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
const int N = 110;
using namespace std;
int n , m;

struct Rice
{
     int price;
     int weight;
     int number;
}rice[N];

int dp[N];

void CompletePack(int cost , int weight)
{
    for(int i = cost;i <= n;i++)
        dp[i] = max(dp[i] , dp[i-cost] + weight);
}

void ZeroOnePack(int cost , int weight)
{
    for(int i = n;i-cost >= 0;i--)
          dp[i] = max(dp[i] , dp[i-cost] + weight);
}

void MultiplePack(int cost , int weight , int number)
{
      if(cost * number >= n)
      {
           CompletePack(cost , weight);
           return;
      }
      int k = 1;
      while(k < number)
      {
           ZeroOnePack(k*cost , k*weight);
           number -= k;
           k *= 2;
      }
      ZeroOnePack(number*cost , number*weight);
}

int main()
{

    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
         scanf("%d%d",&n,&m);
         memset(dp , 0 , sizeof(dp));

         for(int i = 0;i < m;i++)
              scanf("%d%d%d",&rice[i].price,&rice[i].weight,&rice[i].number);
         for(int i = 0;i < m;i++)
               MultiplePack(rice[i].price,rice[i].weight,rice[i].number);

         printf("%d\n",dp[n]);
    }


}

     咱们不妨再来看一道多重背包问题。(Problem source : hdu 1059)

Problem Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
 
Input
Each line in the input describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, ..., n6, where ni is the number of marbles of value i. So, the example from above would be described by the input-line ``1 0 1 2 0 0''. The maximum total number of marbles will be 20000.
The last line of the input file will be ``0 0 0 0 0 0''; do not process this line.
 
Output
For each colletcion, output ``Collection #k:'', where k is the number of the test case, and then either ``Can be divided.'' or ``Can't be divided.''.
Output a blank line after each test case.
Problem Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value. Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
 
  题目大意:给出六个价值分别为一、二、三、四、五、6的物体的数量,让你判断可否能够将物体分红价值相等的两份。
  数理分析:经过阅读该题,咱们会发现如下几个问题。
  1.这道问题并非求解最优策略,而是访问一个子问题的解。
  2.与传统的背包问题相比较,它没有设置费用数组cost[],但它也并非计数类的问题。(紧接着多重背包问题下面给出的三个模型)
  如何解决好这两个问题,是求解这题的关键所在。
  对于题设没有设置费用数组,为了多重背包的正常计算过程,咱们不妨自行定义,假设对于价值为i的物体,咱们须要花费i。并考虑原来咱们设置记录最优解的dp数组的内涵,即dp[i]表示费用为i时可得到的最大价值,那么如今咱们便可作等价转化:当一组价值为sum的物体可以分红价值相等的两组是,其须要知足的充分必要条件是dp[sum/2] = sum/2。
  基于多重背包的模型和这种基于具体问题的灵活转化,这个问题也就迎刃而解了。
  参考代码以下。
 
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int a[7];
int dp[120005];
int v , k;

void ZeroOnePack(int cost , int val)
{
     for(int i = v;i >= cost;i--)
           dp[i] = max(dp[i],dp[i-cost]+val);
}

void CompletePack(int cost , int val)
{
     for(int i = cost; i <= v;i++)
            dp[i] = max(dp[i],dp[i-cost]+val);
}

void MultiplePack(int cost , int val , int amount)
{
      if(cost*amount >= v) CompletePack(cost , val);
      else
      {
          for(int k = 1;k < amount;)
          {
              ZeroOnePack(k*cost , k*val);
              amount -= k;
              k<<=1;
          }
          ZeroOnePack(amount*cost , amount*val);

      }
}

int main()
{
    int tol;
    int iCase = 0;
    while(1)
{
      iCase++;
      tol = 0;
    for(int i = 1;i <= 6;i++)
    {
          scanf("%d",&a[i]);
          tol += a[i]*i;
    }
        if(tol == 0)  break;
        if(tol % 2 == 1)
        {
            printf("Collection #%d:\nCan't be divided.\n\n",iCase);
        }
        else
        {
             v = tol/2;
             memset(dp , 0 , sizeof(dp));
             for(int i = 1;i <= 6;i++)
                   MultiplePack(i , i , a[i]);
             if(dp[v] == v)
                 printf("Collection #%d:\nCan be divided.\n\n",iCase);
             else
                 printf("Collection #%d:\nCan't be divided.\n\n",iCase);
        }
}



}

 

 
 

  经过上文对01背包、彻底背包、多重背包的简单介绍,背包问题中的另一个模型——计数问题。

  考虑这样一个问题,给出n种物体的体积,我有多少种不一样的方案,来刚好装满体积为v的背包?

  那么对应着01背包问题、彻底背包、多重背包,咱们就又能够生成下面三个带有限制的问题。

  模型一:给出n种物体(每种物体只有一个)的体积序列v[],我有多少种不一样的方案,来刚好装满体积为v的背包?(对应01背包模型)

  模型二:给出n种物体的体积序列v[]和数量序列num[],我有多少种不一样的方案数,来刚好装满体积为v的背包?(对应多重背包问题)

  模型三:给出n中物体的体积序列v[],每种物体能够装入背包无限次,那么我有多少种不一样的方案来装满体积为v的背包?(对应彻底背包问题)

  其实学习过组合数学中的生成函数的读者可能会发现,这三个模型是能够经过生成函数来解决的,可是实践代表,在参数值较大的时候,生成函数的效率每每是不及动态规划的,所以这里咱们主要从动态规划的角度来解决以上几个模型。

  首先咱们来分析第三个模型,即对于每种物体没有数量限制的状况。其实对应着分析彻底背包问题的分析思路,因为物体的数量是无限的,因此咱们不会经过枚举数量来找到状态转移方程,而是从背包的体积v出发,这其实就实现了优化,若是像在处理多重背包那样枚举每种物体的数量,咱们须要设置三层循环,然后者只须要两层。咱们设置数组dp[v]是刚好装满体积为v的背包时的方案数,咱们容易看到,咱们依旧从过程分析入手,假设当前正在选第i种物体,当前咱们枚举的背包体积是j,咱们容易获得以下的状态转移方程:                                                              dp[j] += dp[j - v[i]]

  咱们经过一个题目来具体体会一下这个模型的应用。(Problem souce : uva674)

  Suppose there are 5 types of coins:  50-cent, 25-cent, 10-cent, 5-cent, and 1-cent.  We want to make
changes with these coins for a given amount of money.
For example, if we have 11 cents, then we can make changes with one 10-cent coin and one 1-cent
coin, two 5-cent coins and one 1-cent coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins.
So there are four ways of making changes for 11 cents with the above coins. Note that we count that
there is one way of making change for zero cent.
Write a program to find the total number of different ways of making changes for any amount of
money in cents. Your program should be able to handle up to 7489 cents.
Input
The input file contains any number of lines, each one consisting of a number for the amount of money
in cents.
Output
For each input line, output a line containing the number of different ways of making changes with the
above 5 types of coins.

  题目大意:如今有五种硬币面值为一、二、五、2五、50,如今给出整数n,求解经过这五种硬币不限次数的组合出n的方案数。   数理分析:经过比较不难发现,这就是咱们上文分析的模型三,硬币的面值就是物体的体积,而n则是背包的体积。

  参考代码以下:

#include <cstdio>
#include <cstring>
using namespace std;
int const MAX = 8000;

int dp[MAX];
int money[6] = {0,1,5,10,25,50};

int main()
{

int n;

      while(scanf("%d",&n) != EOF)
        {
           memset(dp , 0 , sizeof(dp));
              dp[0] = 1;
           for(int i = 1; i <= 5; i++)
               for(int j = 0; j <= n; j++)
                    dp[j+money[i]] +=  dp[j];
                printf("%d\n",dp[n]);
        }
}

   咱们再来看一道很相似的题目。(Problem source : hdu 1284)

 

Problem Description
在一个国家仅有1分,2分,3分硬币,将钱N兑换成硬币有不少种兑法。请你编程序计算出共有多少种兑法。
 
Input
每行只有一个正整数N,N小于32768。
 
Output
对应每一个输入,输出兑换方法数。
  几乎是和咱们在模型三一开始的讨论中给出的例题如出一辙,代码稍做修饰即可AC,而思惟过程在这里为了防止累述,就不赘言了。
  参考代码以下。
 
#include <cstdio>
#include <cstring>
using namespace std;
int const MAX = 32769;

int dp[MAX];
int money[4] = {0,1,2,3};

int main()
{

int n;

      while(scanf("%d",&n) != EOF)
        {
           memset(dp , 0 , sizeof(dp));
              dp[0] = 1;
           for(int i = 1; i <= 3; i++)
               for(int j = 0; j <= n; j++)
                    dp[j+money[i]] +=  dp[j];
                printf("%d\n",dp[n]);
        }
}

 

 

   咱们不妨再看一道相似的题目。(Problem source : QCU四月月赛D题)

 你们都据说梅小姐喂养了不少兔兔。梅小姐的兔兔超级萌、超级听话,常常能帮助梅小姐AC题目。

有一天,梅小姐给兔兔们一个数字,而后命令兔兔们去寻找有多少个不一样的集合知足集合内的元素相加等于这个数字,而且兔兔们找的每一个数都只能是2的k次幂。

好比: 梅小姐给了一个7:

 

1) 1+1+1+1+1+1+1 

2) 1+1+1+1+1+2 
3) 1+1+1+2+2 
4) 1+1+1+4 
5) 1+2+2+2 

6) 1+2+4 

兔兔们就寻找出这6种状况。

做为萌萌哒的你,也想能拥有兔兔同样的能力,

因而梅小姐给你一个数n,你要立刻回答出有多少种状况知足条件?

 

  经过读题咱们不难发现,这道题目其实就是基于uva674这道题目,只不过这里的币种变成了2^0、2^一、2^二、……2^k,其中2^k < n。

  状态转移方程和uva674是同样的,这里须要注意的是一个编程的小技巧。实践代表,若是咱们每次输入n的时候,都运算一遍,则会显示超时,而若是先将全部的状态给计算出来,再输入n只需对号入座得输出结果,则不显示超时,这代表打表或者说预处理的方法在ACM竞赛中能够很好的缩减运算的时间。

  参考代码以下。

 

#include <cstdio>
#include <cstring>
#include<stdio.h>
#include<math.h>
using namespace std;
int const MAX = 1000000+5;
const int MOD = 1000000007;

int dp[MAX];
int money[MAX];

int main()
{
  int n;


          memset(dp , 0 , sizeof(dp));
            dp[0] = 1;
                  int ans = 0;
                    for(long long i = 0;(ans = pow(2,i)) < MAX ;i++)
                    {
                          for(long long j = ans;j < MAX;j++)
                          {
                               dp[j] += dp[j-ans];
                               dp[j] %= MOD;
                          }
                    }

       while(scanf("%d",&n) != EOF)
           printf("%d\n",dp[n]);
}

 

 

 

 上文中咱们给出了三个关于背包记数的模型,并给出了彻底背包模型的实例,下面咱们来分析多重背包模型,即每种物体拿去的次数是有上限的,对应着上文的模型二。

  因为这种模型给出了每种物体的数量限制,所以咱们有必要枚举每种物体的数量(对比彻底背包,后者就不须要枚举数量,而是直接以体积为标准)。咱们定义二维数组dp[i][v]表示前i个物体刚好装满体积为v的背包的方案数,给出n种物体的体积序列v[],那么咱们依然从过程开始分析,假设咱们如今正在选择第i种物体,数量为k,正在构造的背包体积为v'。经过该状态和上一个状态的递推关系,咱们容易获得状态转移方程:  

                                        dp[i][v'] += dp[i-1][v-k*v[i]]  

   基于对该模型的分析,咱们经过一个具体的问题来实践一下它的应用。(Problem source : Light OJ 1231)   

Description

In a strange shop there are n types of coins of value A1, A2 ... An. C1, C2, ... Cn denote the number of coins of value A1, A2 ... An respectively. You have to find the number of ways you can make K using the coins.

For example, suppose there are three coins 1, 2, 5 and we can use coin 1 at most 3 times, coin 2 at most 2 times and coin 5 at most 1 time. Then if K = 5 the possible ways are:

1112

122

5

So, 5 can be made in 3 ways.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 50) and K (1 ≤ K ≤ 1000). The next line contains 2n integers, denoting A1, A2 ... An, C1, C2 ... Cn (1 ≤ Ai ≤ 100, 1 ≤ Ci ≤ 20). All Ai will be distinct.

Output

For each case, print the case number and the number of ways K can be made. Result can be large, so, print the result modulo 100000007.

咱们容易将该问题和上面的模型联系起来,在编程实现上,注意在状态转移方程构造的时候加上取模过程便可。

  参考代码以下。

#include <cstdio>
#include <cstring>
using namespace std;
int const MAX = 1005;
int const MOD = 1e8 + 7;
int dp[55][MAX];
int num[MAX], money[MAX];

int main()
{
    int T;
    scanf("%d", &T);
    int tt = 0;
   while(T--)
    {
        int n, K;
        scanf("%d %d", &n, &K);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &money[i]);
        for(int i = 1; i <= n; i++)
            scanf("%d", &num[i]);
        dp[0][0]= 1;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= K; j++)
                for(int k = 0; k <= num[i]; k++)
                    if(j - k * money[i] >= 0)
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k * money[i]]) % MOD;
        printf("Case %d: %d\n", ++tt, dp[n][K]);
    }
}

  

 

  既然咱们已经给出了模型二的分析,下面不如再看一道相似的题目。(Problem source : Light OJ 1232)
  

Description

In a strange shop there are n types of coins of value A1, A2 ... An. You have to find the number of ways you can make K using the coins. You can use any coin at most K times.

For example, suppose there are three coins 1, 2, 5. Then if K = 5 the possible ways are:

11111

1112

122

5

So, 5 can be made in 4 ways.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 100) and K (1 ≤ K ≤ 10000). The next line contains n integers, denoting A1, A2 ... An (1 ≤ Ai ≤ 500). All Ai will be distinct.

Output

For each case, print the case number and the number of ways K can be made. Result can be large, so, print the result modulo 100000007.


  题目大意:给出n种硬币的面值,与上面的问题(Light OJ 1231)不一样的是,每一种硬币的数量上限都是k(这里的k同时也表示不一样的硬币组合使得面值之和为k的全部方案数)。
  数理分析:其实咱们很容易上面的Light OJ 1232联系起来,可是咱们发现直接调用代码的话,会返回一个TEL的结果,那么咱们接下来就要考虑优化。
  容易看到,每种硬币的面值是大于等于1的,这里设给出n种硬币的面值序列value[],这就意味着若是k | value[i],那么该种硬币必定存在一种组合来凑齐总值为k,而且这种方案多用的硬币都是第i种硬币,这让咱们天然得联想到,彻底背包问题的模型不也是有这样的状况吗?若将其转化成彻底背包,即可少一层穷举第i种硬币数量的循环,计算效率必然会获得提高。
  基于以上的分析,咱们便将该问题转化成彻底背包的记数问题来处理。因为上文中一开始就给出了分析(对应模型三),这里便再也不累述。
  参考代码以下。

#include <cstdio>
#include <cstring>
using namespace std;
int const MAX = 10005;
int const MOD = 1e8 + 7;
int dp[MAX];
int num[105], money[10];

int main()
{
    int T;
    scanf("%d", &T);
    int tt = 0;
   while(T--)
    {
        int n, K;
        scanf("%d %d", &n, &K);
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &money[i]);

        dp[0]= 1;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= K; j++)
                  dp[j + money[i]] = (dp[j + money[i]] + dp[j])%MOD;
        printf("Case %d: %d\n", ++tt, dp[K]);
    }
}

 

  上文讨论了有关01背包、彻底背包、多重背包的模型及其记数问题,下面咱们来介绍二维费用背包的模型。
  所谓二维费用背包,就是在以上背包问题的基础上,又加了一维限制条件。好比说上文中咱们给出的背包模型,都是继续物品的体积限制,来求得最大的价值数,而咱们再多一维限制,背包不只有重量限制,还有体积限制,而对于每一个物体,这里给出价值val、重量wei、体积v三个参数,限制条件就变成了重量和体积两个量,这即是所谓的二维费用背包。
  容易看到,从维度上,咱们能够讲背包分红一维费用、二维费用甚至多维费用,那么在二维费用背包中势必也有着相似一维背包中的01背包、彻底背包、多重背包等问题,因为前文已经有所介绍,后文便再也不详细的建模分析,而是结合具体的题目进行分析。
  咱们这里暂且拿二维费用背包来分析,与一维背包的分析相似,咱们须要设置dp数组来记录决策过程当中全部的状态,而在二维费用背包中显然有三个参量——选取的物体个数i、当前总质量j、当前整体积k,那么咱们天然而然的设置三维数组dp[i][j][k],来表示选取了i种物体时,体积为j、重量为k时物体价值总和的最大值。那么咱们容易获得状态转移方程以下:
          dp[i][j][k] = max(dp[i-1][j][k] , dp[i-1][j-v[i]][k-wei[i]] + val[i])
  经过与上文各个模型的分析过程咱们能够看出,其实这个状态转移方程是适用于01背包的二维费用背包,而若是出现物体数量不限的条件,咱们也是能够像处理一维的彻底背包问题中那样,下降dp数组的维度。
  咱们经过一个具体的题目来体会一下二维费用(彻底)背包。(Problem source : hdu 2159)
  

Problem Description
最近xhd正在玩一款叫作FATE的游戏,为了获得极品装备,xhd在不停的杀怪作任务。长此以往xhd开始对杀怪产生的厌恶感,但又不得不经过杀怪来升完这最后一级。如今的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会获得相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0如下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗?
 
Input
输入数据有多组,对于每组数据第一行输入n,m,k,s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值,保留的忍耐度,怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a,b(0 < a,b < 20);分别表示杀掉一只这种怪xhd会获得的经验值和会减掉的忍耐度。(每种怪都有无数个)
 
Output
输出升完这级还能保留的最大忍耐度,若是没法升完这级输出-1。
 


  数理分析:经过读题不难发现,在这个问题的决策过程当中,疲劳值和刷怪数是限制条件,而经验值则是咱们想要达到最大的量。题设中有着“每种怪的数量不限”的字眼,咱们很容易知道它是一个彻底背包的问题。
  上文咱们提到,相对于01背包,彻底背包因为其每种物体的数量不限,在编程实现的时候是能够下降维优化的。咱们抛弃其表示dp数组表示已经选入几种物体的那个参量i(经过一层循环来实现对k种物体的选择),设置dp[x][z]来表示消耗疲劳值为x,刷怪数为z时的经验值。
  咱们从x = 1开始日后遍历到疲劳值的最大值m(与之对应的01背包是从后往前遍历,这是这两个模型一个最关键的区别,至于缘由,上文已有所说起)。而后设置一层循环,用于遍历k种不一样的物体,随后再设一层循环,用于遍历当前过程刷怪的数量。
  咱们模拟这个过程,假设咱们在决策疲劳值为x、刷怪数为z、怪是第y种时经验值的最大值的方案,则其知足以下的状态转移方程:
   dp[x][z] = max(dp[x][z],dp[x-cnt*wei[y]][z - cnt] + cnt*val[y])
  其中cnt表示当前方案中第y种怪刷了多少只。
  基于以上的数理分析,咱们就不难进行编程实现了。
  参考代码以下。

 

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;

struct node
{
      int wei , val;
}a[155];

  int dp[155][155];

  int main()
  {
        int n , m , k , s , x , y , z , i;
        while(~scanf("%d%d%d%d",&n,&m,&k,&s))
        {
              for(i = 1;i <= k;i++)
                  scanf("%d%d",&a[i].val , &a[i].wei);
              memset(dp , 0 , sizeof(dp));

              for(x = 1;x <= m;x++)
              {
                   for(y  = 1;y <= k;y++)
                   {
                        for(z = 1;z <= s;z++)
                        {
                              int cnt = 1;
                              while(cnt*a[y].wei <= x && cnt <= z)  //模拟彻底背包
                              {
                                  dp[x][z] = max(dp[x][z] , dp[x-cnt*a[y].wei][z-cnt] + cnt*a[y].val);
                                  cnt++;
                              }
                        }
                   }
                   if(dp[x][s] >= n)
                    break;
              }

              if(x > m)  printf("-1\n");
              else       printf("%d\n",m-x);

        }
  }

 

  

  咱们不妨再来看一个二维费用的背包问题。(Problem source : hdu 1963)
  

Description

John never knew he had a grand-uncle, until he received the notary's letter. He learned that his late grand-uncle had gathered a lot of money, somewhere in South-America, and that John was the only inheritor. John did not need that much money for the moment. But he realized that it would be a good idea to store this capital in a safe place, and have it grow until he decided to retire. The bank convinced him that a certain kind of bond was interesting for him. This kind of bond has a fixed value, and gives a fixed amount of yearly interest, payed to the owner at the end of each year. The bond has no fixed term. Bonds are available in different sizes. The larger ones usually give a better interest. Soon John realized that the optimal set of bonds to buy was not trivial to figure out. Moreover, after a few years his capital would have grown, and the schedule had to be re-evaluated. Assume the following bonds are available:
Value Annual interest
4000 3000 400 250
With a capital of e10 000 one could buy two bonds of $4 000, giving a yearly interest of $800. Buying two bonds of $3 000, and one of $4 000 is a better idea, as it gives a yearly interest of $900. After two years the capital has grown to $11 800, and it makes sense to sell a $3 000 one and buy a $4 000 one, so the annual interest grows to $1 050. This is where this story grows unlikely: the bank does not charge for buying and selling bonds. Next year the total sum is $12 850, which allows for three times $4 000, giving a yearly interest of $1 200. Here is your problem: given an amount to begin with, a number of years, and a set of bonds with their values and interests, find out how big the amount may grow in the given period, using the best schedule for buying and selling bonds.

Input

The first line contains a single positive integer N which is the number of test cases. The test cases follow. The first line of a test case contains two positive integers: the amount to start with (at most $1 000 000), and the number of years the capital may grow (at most 40). The following line contains a single number: the number d (1 <= d <= 10) of available bonds. The next d lines each contain the description of a bond. The description of a bond consists of two positive integers: the value of the bond, and the yearly interest for that bond. The value of a bond is always a multiple of $1 000. The interest of a bond is never more than 10% of its value.

Output

For each test case, output – on a separate line – the capital at the end of the period, after an optimal schedule of buying and selling.


  题目大意:给出本金money和买期货的年数y,而后给出d种期货的价格及其一年的利息,求解y年后的最大本息和。
  数理分析:经过与典型的背包问题的比较,咱们不难发现,这里期货的价格是费用,而利息则是价值。而在这个题目中其实还有另一层费用——买期货的年数。所以这是一个较为典型的二维背包问题。
  若是暂且抛却这个问题的第二维费用,咱们能够看到对于某种期货,若是钱数够用的,该种期货是能够买不少的,由此咱们能够判断这个二维费用背包是在彻底背包的基础上创建起来的。
  随后咱们考虑第二维费用,基于整个交易的机制——当年年末清算,所以咱们首先经过彻底背包模型来找到第一年后的最大本息和,而后再以此为本金,找到第二年后的最大本息和,循环操做,不难找到第n年后的最大本息和,即该题的答案。
  值得注意的是,题设申明了期货的价格都是1000的整数倍,这有什么用处呢?这是由于,在通常的彻底背包的求解思路中,咱们设置的dp[i]是表示费用为i时的最大价值数,而在这道题目中费用的数量级他大,为了防止爆内存,咱们只需将初始的本金和每种期货的价格除以1000以下降费用的数量级,同时也不会影响dp数组值的正确求解。
  基于以上的分析,咱们便不难进行编程实现了。
  参考代码以下。
 

    在背包问题中,若是咱们将n个物体分红k组,每组中的各个物体因为某些实际缘由,没法同时选入背包中,也就是说每组至多能选出一个物体放入背包,那么咱们如何求解最优方案呢?
  其实相似于01背包,咱们设置dp[i][j]表示选了i组、容量为j时物体价值的最大数,咱们容易获得以下的状态转移方程。
         dp[i][j] = max(dp[i-1][j]  , dp[i-1][j-wei[i][k]]+v[i][k])

  其中wei[i][k]表示第i组物体中第k件物体的重量,v[i][k]则表示第i组物体中第k件物体的价值。
  咱们一样能够经过外设一层枚举当前方案选择第i组物体的循环,来为dp数组下降维度。那么咱们设置dp[j]储存容量为j的背包最优解。
  假设咱们当前在选择第i组,容易看到,在对第i组的每一个物体进行选择的时候,咱们其实开始模拟了01背包的过程,所以咱们再设一层循环有来枚举背包的容积,因为其实01背包的模型,咱们令j = v_of_pack,而且经过j--来实现遍历。
  基于这两层循环,咱们只需再设置一层循环,用来遍历第i组的每一个物体便可。咱们假设当前遍历到第i组第k个物体,此时背包的容积为j,那么显然有以下的状态转移方程:
     dp[j] = max(dp[j],dp[j-wei[i][k] + v[i][k]])。
  这个过程能够经过以下的伪码很好的归纳。
  for k = 1 to K
      for v = V to 0
             for item i in group k
                F[v] = max{F[v],F[v−Ci] + Wi}
  咱们来结合一个具体的题目来真正实现一下分组背包问题的求解方案。(Problem source : hdu1712)
 

Problem Description
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
 
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has. Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j]. N = 0 and M = 0 ends the input.
 
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.


  题目大意:给出变量n、m分别表示有n种课程和m天,而后给出矩阵A,A[i][j]表示花费j天到第i个课程上的效益,须要咱们求解在m天中能够得到的最大效益是多少。
  数理分析:基于上文对分组背包模型的分析,这里值得咱们注意的就是如何讲将一个实际问题转化到咱们已经解决的模型上来。
  咱们容易看到,就题目而言,对于第i种课,咱们是没法读两次的,所以这n种课其实就是n组,每组中的m种方案至多只能选出一种。而拥有的天数显然是背包的容积,经过题目对矩阵内涵的解释,咱们也容易获得记录费用的wei[]和记录价值的val[]。
  基于以上对模型的转化,再结合上文对分组背包模型的详细分析,咱们就不难进行编程实现了。
  参考代码以下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[105];

struct node
{
     int w , v;
};

node g[105][105];

int main()
{
      int n , m;
      while(scanf("%d%d",&n,&m) != EOF)
      {
            int i , j , k;
            if(n == 0 && m == 0 )  break;
        memset(dp , 0 , sizeof(dp));
        memset(g , 0 , sizeof(g));
        for(i = 1  ;i <= n;i++)
             for(j = 1;j <= m;j++)
        {
                scanf("%d",&g[i][j].v);
                g[i][j].w = j;

        }

        for(i = 1 ;i <= n;i++)
        {
              for(j = m;j>=0;j--)  //模拟01背包
              {
                    for(k = 1;k <= m;k++)
                    {
                          if(j>=g[i][k].w)
                              dp[j] = max(dp[j] , dp[j-g[i][k].w] + g[i][k].v);
                    }
              }
        }
        printf("%d\n",dp[m]);
      }
}

 

 

  

  其实经过上文对背包问题的探讨,其不少类型的背包问题都是有多个简单的模型结合在一块儿的,最简单的例子就是多重背包问题其实就能够看错01背包和彻底背包的结合。包括咱们讨论过的分组背包,咱们也可以看到01背包的模型。   那么咱们今天再来看其中杂糅了01背包的背包问题——依赖背包模型。

  依赖背包问题的模型很简单,就是说对于某个物体,将它装入背包必须以装入一个物体作前提。这其实十分相似咱们上文提到的分组背包问题。咱们将那些没有依赖性的物体成为“主件”,而那些有依赖性的物体成为“附件”,那么咱们容易看到,若是将物体分组,咱们能够将其分红n组,其中n是“主件”的数量,而在每一组中,咱们以这个主件为根节点,那些依赖“主件”的物体,咱们将其看作这个根节点下面的树。

  那么下面咱们要作的就是模拟整个决策过程并维持最优解了。在这个问题中,每种状态的方案有两个参量,即已经选择的树的数量和此时背包的容积,所以咱们设置二维数组dp[i][j]来表示选择i棵树且背包容积为j时物体价值的最大数。

  那么咱们从中间的过程开始分析,容易看到,其实依赖背包能够当作关于每棵树的双重01背包决策,第一层是关于这棵树根节点的决策,第二重则是关于这棵树的树叶的决策。   假设当前正在计算第i棵树,背包容量为j的方案数。则出现如下两种状况。

  ①选择第i棵树的根节点,则dp[i][j] = dp[i][j-root[i]]。由于已经选入个根节点,那么显然第i棵树的其余树叶也能够选了,即对第i棵树的剩余叶节点使用01背包的决策方略,即dp[i][j] = dp[i][j-cost[k]],其中cost[k]表示第i棵树的第k片叶子的费用。

  ②那么若是不选入第i棵树的根节点呢?那么咱们经过比较dp[i][j]和dp[i][j-1]的大小便知道选入第i棵树的根节点是不是最优方案。若是dp[i-1][j] > dp[i][j],那么代表在选择第i-1棵树时,构造相同容积的背包,有着比选入第i棵树根节点更优的方案,那么此时咱们就不须要再保存选入第i棵树根节点的方案了。间接的来讲,能够用以下的状态转移方程来表达上述内容。

        dp[i][j] = max(dp[i][j],dp[i-1][j])

  至此,就完成了对一棵树的双重01背包决策,那么遍历n棵树,最优解就天然而然的解出来了。

  咱们经过一道具体的题目来实现依赖背包的算法。(Problem source : hdu 3449)  

Problem Description
FJ is going to do some shopping, and before that, he needs some boxes to carry the different kinds of stuff he is going to buy. Each box is assigned to carry some specific kinds of stuff (that is to say, if he is going to buy one of these stuff, he has to buy the box beforehand). Each kind of stuff has its own value. Now FJ only has an amount of W dollars for shopping, he intends to get the highest value with the money.
 
Input
The first line will contain two integers, n (the number of boxes 1 <= n <= 50), w (the amount of money FJ has, 1 <= w <= 100000) Then n lines follow. Each line contains the following number pi (the price of the ith box 1<=pi<=1000), mi (1<=mi<=10 the number goods ith box can carry), and mi pairs of numbers, the price cj (1<=cj<=100), the value vj(1<=vj<=1000000)
 
Output
For each test case, output the maximum value FJ can get

  题目大意:给出n个箱子的价格,和每一个箱子当中的物体的费用和价值,买物品必须依赖买箱子,而后给出money表示你拥有的资金,求解可以获得最大价值的方案数。

  数理分析:不难看到,这里的箱子其实就是n棵树的根节点,而其中的物体则是根节点下的叶子,经过上述对依赖背包模型的分析,不难进行编程实现。

  值得注意的是,因为这里数据较多,在编程的时候咱们能够基于动态规划自己的特色,即传入一组参数dp数组就更新维护一次最优解,咱们能够输入一组数据,进行动态规划的求解。

  参考代码以下。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Ni = 55;
const int Mi = 100005;
int dp[Ni][Mi];

int main()
{
       int n , m , money , i , j , k , box , cost , val;
       memset(dp[0] , 0 , sizeof(dp[0]));

       while(scanf("%d%d",&n,&money) != EOF)
       {
               for(i = 1;i <= n;i++)
               {
                     scanf("%d%d",&box,&m);
                     for(j = 0;j < box;j++)  dp[i][j] = -1;
                     for(j = money;j>=box;j--)  dp[i][j] = dp[i-1][j-box];//对于根的01背包,选择根
                     for(k = 1;k <= m;k++)
                     {
                           scanf("%d%d",&cost,&val);
                             for(j = money;j>=cost;j--)
                             {
                                   if(dp[i][j-cost] != -1) //对于叶的01背包
                                      dp[i][j] = max(dp[i][j],dp[i][j-cost]+val);
                             }

                     }
                           for(j = money;j >= 0;j--)//对于根的01背包,维持最优解,判断是否应该选择根
                                  dp[i][j] = max(dp[i][j] , dp[i-1][j]);


               }
               printf("%d\n",dp[n][money]);
       }
}

 

参考系:《背包九讲》——崔添翼


 
 


 

转载于:https://www.cnblogs.com/rhythmic/p/5285437.html