资源分配类动态规划

机器分配总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。分析用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1=I=N,1=J=M,0=K=J)初始值:F(0,0)=0时间复杂度O(N*M2)系统可靠性一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。样例输入文件格式：第一行：nC第二行：C1P1(0)P1(1)…P1(X1)（0=X1=[C/Ck]）…第n行：CnPn(0)Pn(1)…Pn(Xn)（0=Xn=[C/Cn]）输入：22030.60.650.70.750.80.850.950.70.750.80.80.90.95输出：0.6375分析设F[i,money]表示将money的资金用到前I项备用件中去的最大可靠性，则有F[i,money]=max{F[i-1,money–k*Cost[i]]*P[i,k]}(0=i=n,0=K=moneydivCost(i))初始：F[0,0]=0目标：F[n,C]快餐问题Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。分析本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状态表示：用p[i,j,k]表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用r[i,j,k]表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。态转移方程：p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}(0=j1=j=100,0=k1=k=100,且(j-j1)*p1+(k-k1)*p2=T[i]---第i条生产线的时间)r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的时间复杂度为O(N*1004),优化在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min｛100divA，100divB，100divc｝），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。金明的预算方案金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图书书桌台灯，文具工作椅无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件budget.in的第1行，为两个正整数，用一个空格隔开：nm（其中N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数vpq（其中v表示该物品的价格（v10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q0，表示该物品为附件，q是所属主件的编号）【输出文件】输出文件budget.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（200000）。假设只有主件的情况给出m件物品和n元钱，每个物品有一个费用Ci和价值Vi，问买哪些东西能使得所购写的物品的价值和最大。用F[i,j]表示在前i件物品中选择一些，使所花的钱数不超过j时所得的最大价值。则F[0,j]=F[i,0]=0(边界条件)F[i,j]=max{F[i-1,j],F[i-1,j-Ci]+Vi}此算法的复杂度为O(nm)。回到原题假设一件物品i有t种附件选择方案，费用分别为Ci1..Cit，价值分别为Vi1..Vit，则ikikF[i-1,j],(i)[,]maxF[i-1,j-C]+V(ik)Fij不选物品选物品的第种附件方案由于每个物品不超过两个附件，所以附件的选择方案非常有限，只要手工枚举一下就可以了。当然，巧妙的做法是：为不够两件附件的物品增加费用和价值都为0的虚物品，使每件物品的附件数都是2。然后分别枚举2个附件选还是不选。这个方法的复杂度仍为O(nm)，可以很好的解决本题了这个资源分配类的dp，我感觉有个通式F(j)(=i)=best{f(j1)(k1)+f(j2)(k2)}==(j1+j2=j|k1,k2=i可调范围区域)注释：i为阶段，j为分配的资源。例1分钱例2分钱例3分本机器的时间*例4分体积。属于同一种