题目描述
采每一株草药都需要一些时间,每一株草药也有它自身的价值,给你一段时间,在这段时间里,让采到的草药的总价值最大。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
思路
O(nm)
和开心的金明一样都是01背包,对于每颗草药有两种选择,选或不选,再用滚动数组优化。
var
n,m,i,j:longint;
a,b,f:
array[
0..
1000]
of longint;
begin
read(n,m);
for i:=
1 to m
do
read(a[i],b[i]);
for i:=
1 to m
do
for j:=n
downto a[i]
do
if f[j-a[i]]+b[i]>f[j]
then
f[j]:=f[j-a[i]]+b[i];
writeln(f[n]);
end.
转载请注明原文地址: https://ju.6miu.com/read-149815.html