UC知道求算法。。noip动态规划的题。。。。要C语言的!!!!!!!!
来源：百度知道 编辑：UC知道 时间：2024/05/17 08:55:42
资源分配问题
设有资源a分配给n个项目，gi(x)是数量为x（x<=a）的资源分配给项目i所能得到的利润，i=1，2，…，n最合理的资源分配导致解下面的问题：
max Z=g1(x1)+g2(x2)+…+gn(xn) 其中x1+x2+…+xn=a xi>=0，i=1，2，…，n。
例如：有7万元资本投资到A、B、C三种项目，其利润见表。
投资额
项目 1 2 3 4 5 6 7
A 0.12 0.15 0.20 0.21 0.24 0.30 0.36
B 0.22 0.24 0.26 0.28 0.30 0.33 0.34
C 0.18 0.22 0.26 0.28 0.30 0.34 0.36
设有资源a分配给n个项目，gi(x)是数量为x（x<=a）的资源分配给项目i所能得到的利润，i=1，2，…，n最合理的资源分配导致解下面的问题：
max Z=g1(x1)+g2(x2)+…+gn(xn) 其中x1+x2+…+xn=a xi>=0，i=1，2，…，n。
例如：有7万元资本投资到A、B、C三种项目，其利润见表。
投资额
项目 1 2 3 4 5 6 7
A 0.12 0.15 0.20 0.21 0.24 0.30 0.36
B 0.22 0.24 0.26 0.28 0.30 0.33 0.34
C 0.18 0.22 0.26 0.28 0.30 0.34 0.36
设f[i,k]是将i万元投资到前k个项目得到的最高利润。
比如f[7,3]就是将7万元投资到前3个项目所得到的利润
那么你要得到的结果就是f[a,n]的数值罢了
根据题意
f[i,k]的递推公式可以写为
f[i,k]=max(f[i-j,k-1]+gk[j]) {j=1……i-1}
具体的实现过程就要你自己写了
算法就是这样，很简单的题
做动态规划的题,关键是找准状态,这个状态必须有最优子结构的特性,
以及无后效性,意思是后面做的决策不能影响前面的状态
这样子我们把每个状态的最优值都找到并储存下来,这样最后的状态,
也就是全局状态的最优值也就有了.
说白了,动态规划是一种以空间上的开销来节约时间上开销的方法
我这里还没找到 好的状态 这个是关键