资源分配类动态规划.ppt

《资源分配类动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、机器分配总公司拥有高效生产设备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

2、，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(X

3、1)（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市开了一家快餐店，为了

4、招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,

5、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]

6、=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条流水线可以生产的套数，并与上限

7、比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。金明的预算方案金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是

8、从属于某个主件的，下表就是一些主件与附件的例子：主件附件电脑打印机，扫描仪书柜图