文档介绍：动态规划转移方程 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个饮料组成。价格便宜。为了提高产量,Pete r从著名的麦当劳公司引进了 N条生产线。所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡, 薯条和饮料的单位生产时间又不同。这使得 Peter 很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过 100 个。输入: 输入文件共四行。第一行为三个不超过 100 的正整数 A、B、C中间以一个空格分开。第三行为 3个不超过 100 的正整数 p1,p2,p3 分别为汉堡,薯条和饮料的单位生产耗时。中间以一个空格分开。第