大家好，欢迎来到IT知识分享网。
今天开始进入了动态规划的专题学习。
动态规划(dynamic programming)，是运筹学的一个分支，其主要用于寻找最优方案。说到最优方案，我们不禁要将其与一种最基本的算法——贪心算法，联系起来。事实上，正是由于这种共性，使得很多问题有着多解性。
百度百科中有着这样一句话：“20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。”这其实也就点出了动态规划的精髓所在——多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。而落实到具体解决问题的过程中，其实就是寻求状态转移方程的过程。
上面先从整体上来概述了一下动态规划的思想，下面我们通过算法世界里经典的背包问题来具体的体会这种思想。
首先我们先对背包问题有一个概述，有n个物品，第i个物体的重量是w[i],价值是v[i]，在给定承重为m的背包中，放入物体，求解所有的方案中，物体总价值最大的那一种。这便是最原始的背包问题，而基于选择物品的种种限制条件不同，背包问题又可以分为很多类型，这里暂时不一一列举，我们会在后面的文章中分析到。
01背包问题。
在这个问题中，对于每个物体，只允许存在两个状态：不装入背包或者仅仅装入1个，从这里其实也能够理解01背包这个名称的由来，因为物体只对应这0或1这2种状态。
下面我们开始分解决策过程以寻求各阶段之间的关系并得到状态转移方程。我们从决策的过程中开始分析，假设我们当前正在选择第i个物品，那么我们决策的结果有如下两种情况。
①将第i个物品装入背包当中。
②不将第i个物品装入背包当中。
针对①情况，我们必须基于前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)
31).
参考代码如下。
#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)
n=0表示数据结束。
数理分析：通过读题后，发现这个问题无法与我们上文给出的模型完全对应起来，因为，在这个问题中，显然要把每一种菜当做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)
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.
题目大意：给出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)
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.
题目大意：给出参量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
后面的m行，每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
梳理一下该题的数据我们不难发现，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、1、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)
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!
题目大意：给出一个储钱罐空载时和满载时的容量，然后给你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)
当然，为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。
接下来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)
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!
题目大意：英雄和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)
后记： 人生是一个充满了变数的生命过程，天灾、人祸、病痛是我们生命历程中不可预知的威胁。 月有阴晴圆缺，人有旦夕祸福，未来对于我们而言是一个未知数。那么，我们要做的就应该是珍惜现在，感恩生活—— 感谢父母，他们给予我们生命，抚养我们成人； 感谢老师，他们授给我们知识，教我们做人 感谢朋友，他们让我们感受到世界的温暖； 感谢对手，他们令我们不断进取、努力。 同样，我们也要感谢痛苦与艰辛带给我们的财富～
题目大意：很明显的多重背包问题。
数理分析：详细的分析在上文中已经呈现，这里便不再赘述。
参考代码如下。
#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)
The last line of the input file will be “0 0 0 0 0 0”; do not process this line.
Output a blank line after each test case.
题目大意：给出六个价值分别为1、2、3、4、5、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.
题目大意：现在有五种硬币面值为1、2、5、25、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)
#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^1、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)
数理分析：通过读题不难发现，在这个问题的决策过程中，疲劳值和刷怪数是限制条件，而经验值则是我们想要达到最大的量。题设中有着“每种怪的数量不限”的字眼，我们很容易知道它是一个完全背包的问题。
上文我们提到，相对于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
| Value | Annual interest |
| 4000 3000 | 400 250 |
Input
Output
题目大意：给出本金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)
题目大意：给出变量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)
题目大意：给出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://yundeesoft.com/34078.html
