[工学]动态规划题

《[工学]动态规划题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划在信息学奥林匹克竞赛中的应用*************************************************************************快餐问题问题描述：Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套由A个汉堡、B个薯条、C个饮料组成。价格便宜。为了提高产量，Peter从麦当劳公司引进了N条生产线。所有的生产线都能生产汉堡、薯条、饮料，由于每条生产线能提供的生产时间是有限的，不同的，而生产汉堡、薯条、饮料的单位生产时间不同，这使得Peter很为难，不知如何安排生产才能使一天中生产的套餐产量最大。请你编程，计算一

2、天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。解：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,i-j1,k-k1]}其中j1,k1的范围：0<=j1<=j,0<=k1<=k，且生产k1个薯条、j1个汉堡的时间不大于生产线i的使用时间。******************************************************************

3、*******机器分配问题描述：某工厂购进1000台机器,准备生产P1、P2两种产品。若生产P1产品，每台机器可收入50千元，损坏率达65%,若生产P2产品，每台机器可收入40千元，但损坏率为40%。估计三年后将有新的机器出现，旧的机器将全部淘汰，试问应如何安排生产，使三年收入最多？计划以年为周期。解:应用最佳原理,变成多阶段判决问题.设:Pi(n)表示n台机器在最后的i年内最大的收益.问题就是求P3(1000).若只考虑1年的生产安排即最后一年的生产，设x3为生产P1产品的机器数，则P1(n)=max{5000*X3+(n-x3)*4000}其中0<=X3<=nP1(n)=5000n,x

4、3=n，即最后一年，全部机器用于生产P1产品。若考虑2年的生产，即最后二年的生产，设x2为两年中第一年生产P1产品的机器数，则P2(n)=max{5000*x2+4000*(n-x2)+P1(0.35x2+0.60(n-x2)}其中0<=X2<=nP2(n)=max{70000n-2500x2},x2=0，即全部机器用于生产P2产品。若考虑3年的生产，设三年中第一年生产P1的机器数设为x1，则P3(n)=max{5000*x1+4000*(n-x1)+P2(0.35x1+0.60(n-x1)}其中0<=X1<=1000P3(n)=max{82000000-75x1},x1=0，即全部机器生

5、产P2产品。所以第一年，全部机器生产P2产品，第二年，全部机器生产P2产品，第三年，全部机器生产P1产品。总收入82000000元。*************************************************************************N个数的和问题描述：已知N个数,和一个数M求这N个数中的那些加和等于M,或者最接近M,或者是在小于M时最大请问这类问题应该用哪部分知识解答,有什么高效算法吗?(N<100000,m<100000)可用类似于法码称重的动态规划。阶段：以N个数的次序为阶段，设fi(k)表示仅考虑前i个数，加法起来是否可以是k，是fi(k

6、)＝True，否Fasle；状态：每个阶段有100000个状态，fi(k),(0

7、一个公司举行宴会，为了使宴会愉快，老板决定不同时邀请一个员工和他的上司。这个公司员工结构呈树形，即每个员工只有一个上司，一个员工可能有1个或多个上司，也可能没有。每个员工都有一个气氛值（大于-128小于127），每邀请一个员工，整个宴会的气氛值就会改变。任务是求宴会能达到的最大的气氛值。输入：　员工数n，每个员工的气氛值。接下来是一对数k，l表示l是k的上司。这对数以00结束输出：最大的气氛值样例：输入711111111