文档介绍：动态规划转移方程
1. 资源问题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]+w[i,j-k])
 
2. 资源问题2
------01背包问题
有N件物品和一个容量为V的背包。第i件物品的费用是c,价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);
 
3. 线性动态规划1
-----朴素最长非降子序列
设有由n个不相同的整数组成的数列, 记为:
a(1),a(2),……,a(n)且a(i)<>a(j)   (i<>j)
例如3,18,7,14,10,12,23,41,16,24。
若存在i1<I2<I3< span < ie …>且有a(i1)<A(I2)< span …<a(ie)<>则称为长度为e的不下降序列。如上例中3,18,23,24就是一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。程序要求,当原数列给出之后,求出最长的不下降序列。
F[i]:=max{f[j]+1}
 
4. 剖分问题1
-----石子合并
在一个园形操场的四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆。规定
     
每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
      编一程序,由文件读入堆数N及每堆的石子数(≤20)。
F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);
 
5. 剖分问题2
-----多边形剖分
,在计算机图形学、模式识别和地理数据库方面有重要应用.
F[I,j]:=min(f[j,k]+f[k,j]+a[k]*a[j]*a[i]);
 
6. 剖分问题3
------乘积最大
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:312, 当N=3,K=1时会有以下两种分法:
1)    3*12=36
2)   31*2=62
  
   这时,符合题目要求的结果是:31*2=62
   现在,请你帮助你的好朋友XZ设计一个程序,求得正确的答案。
 
f[i,j]:=max(f[k,j-1]*mult[k,i]);
 
7. 资源问题3
-----系统可靠性(完全背包)
有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c,价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]}
 
8. 贪心的动态规划1
-----快餐问题
一、问题描述
Peter最近在R市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由A个汉堡,B个薯条和C个饮料组成。价格便宜。为了提高产量,Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡,薯条和饮料的单位生产时间又不同。这使得Peter很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过100个。
输入:
输入文件共四行。第一行为三个不超过100的正整数A、B、C中间以一个空格