題意

在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。

分析

設(shè) f[i,j]表示前i件物品，總重量不超過j的最優(yōu)價(jià)值

則 f[i，j]=max{f[i－1，j-w[i]]+P[i]，f[i－1，j]）（1<=i<=m,1<=j<=t,j>=w[i]）順推

F[m,t]即為最優(yōu)解

var

t,m,i,j:longint;
w:array[1..1000]of longint;
p:array[1..100]of longint;
f:array[0..100,0..1000]of longint;
begin
? ? read(t);read(m);
? ? for i:=1 to m do
? ? readln(w[i],p[i]);
? ? fillchar(f,sizeof(f),0);
? ? for i:=1 to m do
? ? begin
? ? ? ? for j:=1 to t do
? ? ? ? begin
? ? ? ? ? ? f[i,j]:=f[i-1,j];
? ? ? ? ? ? if (w[i]<=j)and(f[i,j]<=f[i-1,j-w[i]]+p[i]) then f[i,j]:=f[i-1,j-w[i]]+p[i];
? ? ? ? end;
? ? end;
? ? write(f[m,t]);
end.

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9500175.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的采药:顺推法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。