Pascal动态规划,机器分配问题。

2024-12-20 06:41:26
推荐回答(3个)
回答1:

题目有误,正确的是:
题目描述:总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M<=15,N<=10。分配原则:每个公司有权获得任意数目的设备,但总台数不得超过总设备数M。
数据文件格式为:第一行保存两个数,第一个数是设备台数M,第二个数是分公司数N。接下来是一个 N * M (注意)的矩阵,表明了第I个公司分配J台机器的盈利。
这题我没用动规做(我也不会),我的思路是这样的:
1:读入数据,分别存储在M,N,F[1..N,1..M]上。
2:计算性价比(i公司分配j台机器性价比即F[i,j]/j),存在a[i,j]上。
3:使k:=M;
4:选择 i,j,使a[i,j]最大且i<=k(如有多个最大值取i最大者)。
5:把i,j记录下来。
6:k:=k-i。
7:如k>0,跳第4步。
8:输出(就是之前记录的那些i,j,每组i,j表示第i公司分配j台机器)。
程序我就不附了,自己练练手吧,我要睡了。
---又及,上面的方程F[i,j]=Max(F[i,j],F[i-1,j-k]+a[i,k])左右都有f[i,j],你最好看一下是否是包括在循环里的,我反正觉着有问题。思路不完全对,随时更正。

回答2:

f[i,j]表示与自己比较,在自己的过程中找到最大值,不可能牵扯到前一个公司的

回答3:

题目对的
就是个叠加的
你的方程式就错位了