题目描述
金明希望在不超过N元的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。输出不超过总钱数的物品的价格与重要度乘积的总和的最大值。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
思路
O(nm)
每件物品只能买一次，s是每件物品的总和，方程是:
f[j]:=max(f[j],f[j-a[i]]+s[i]);
var
n,m,i,j:longint;
a,b,s,f:
array[
0..
30000]
of longint;
begin
readln(n,m);
for i:=
1 to m
do
begin
readln(a[i],b[i]);
s[i]:=a[i]*b[i];
end;
for i:=
1 to m
do
for j:=n
downto a[i]
do
if f[j-a[i]]+s[i]>f[j]
then
f[j]:=f[j-a[i]]+s[i];
writeln(f[n]);
end.
转载请注明原文地址: https://ju.6miu.com/read-149789.html
