題意
在規定的時間内,可以采到的草藥的最大總價值。
分析
設 f[i,j]表示前i件物品,總重量不超過j的最優價值
則 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]即為最優解
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.
轉載于:https://www.cnblogs.com/YYC-0304/p/9500175.html