题目描述
金明希望在不超过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]);
varn,m,i,j:longint;a,b,s,f:array[0..30000] of longint;
beginreadln(n,m);for i:=1 to m dobeginreadln(a[i],b[i]);s[i]:=a[i]*b[i];end;for i:=1 to m dofor j:=n downto a[i] doif f[j-a[i]]+s[i]>f[j] thenf[j]:=f[j-a[i]]+s[i];writeln(f[n]);
end.