动态规划练习3

学习档案 | 2013-06-25 12:39:25 | 阅读 1547 次 | 评论(0)

引题 http://bbs.bccn.net/viewthread.php?tid=414177&extra=&page=1
加工工件获取最大价值的问题,为了便于理解学习核心的部分,把题目分解:
开始时间,结束时间,加工工件价值,分别用三个数组表示。
以结束时间排序好。
动态转移方程直接在递归式中表现。 f(i,j)表示至第i个工件时结束时间为j时
累加最大价值。
主要意思是,选取第i个工件时,和不取第i个工件时情况的价值中取较大值。
通俗的讲,当取第i个工件时,此时选取后的 j 值为第i个工件的开始时间,不选 i工件 时此时的j值为(i-1)工件的结束时间。

#include<stdio.h>

int start[]={1,6,8,11};
int end[]={8,8,11,12};//已升序。
int value[]={10,22,103,4};
int f(int i,int j)
{
int l,r,t;
if(i==-1 || j<end[0] ) return 0;//

if(j<end[i]) t= f(i-1,j-(j-end[i-1]));//不能选I 
if(j>=end[i]) //选取大值 
{
   l = f(i-1,j-(j-end[i-1]));   
   r=f(i-1,j-(j-start[i]) )+value[i];
   t=l>r?l:r;
   }
   return t;     

}
int main()
{
printf("%d",f(4,12));
return 0;
}

文章评论,共0条
游客请输入验证码
浏览176864次
最新评论
  • zhouwenyuan:博主可以开发房产APP吗?
  • qunxingw:结合附件,在分表A或B...实验一下宏就理解了
  • qunxingw:这仅是小范围的一种思路,此题是指数级的数据。