#9 linshutan@2008-10-30 00:54:00
7747
回复
删除
我不是牛..简单讲一下.
设f[i,j]表示第一个锅到I时间,第二个锅到J时间的时候的最大值.
则每个状态可以
当j>=第I个物品的结束时
f[j,k]:=max(f[j,k],f[a[i].start-1,k]+a[i].w);
其中start-1很重要..
当k>=第I个物品的结束时时同理.
但因为当且仅当j=a[i].start或k=a[i].start时,药材才会被放入坩锅内,且保证了同一种药品不会在以后被多次放入或者是同时放入二个坩锅,当然,仅仅是这样还是不能保证能求出最优解,因为在计算过程中,结构会被刷新,因此对于结束时间较晚的药材,若在结束时间较前的药材先被计算,则较前的药材就以为价值小而不会被记录,因此就应该在动态规划之前将数据按结束时间a[i].final(即结束时间)升序排序。
for i:=1 to n do
begin
for k:=t downto 0 do
for j:=t downto 0 do
begin
if j>=a[i].final then f[j,k]:=max(f[j,k],f[a[i].start-1,k]+a[i].w);
if k>=a[i].final then f[j,k]:=max(f[j,a[i].start-1]+a[i].w,f[j,k]);
end;
end;
还不懂说..我尽量解答,