题目描述
DaA 和他的朋友组成一个团队去旅行了。他们每个人都准备了一个背包，用来装旅行用的物品。他们的背包有两个特点： 1. 每个人的背包能装无限多的物品，每种物品有一个价值，但只能装一件； 2. 每个人都很有个性，所以每个人的背包不会完全相同。 DaA 的团队中有M 个人，那么对于整个团队，背包价值和最大是多少呢？
输入
第一行两个整数M、N，表示团队的人数和物品的数量。 接下来一行N 个整数，表示每件物品的价值wi。 数据保证不会出现有空背包人的出现。
输出
一个整数，整个团队背包价值的最大值。
样例输入
Sample Input 1: 2 3 2 7 1
Sample Input 2: 8 4 1 2 3 4
样例输出
Sample Output 1: 19
Sample Output 2: 58
数据范围限制
【数据规模】 30%的数据 1<=M,N<=15。 60%的数据 1<=M<=200，1<=N<=100。 100%的数据 1<=M<=1,000,000，1<=N<=500，0< wi<=50。 输出请注意使用64 位整数（Pascal 中的Int64，C++中的long long）。
提示
【样例解释】 19=(2+7+1)+(2+7) 58=(1+2+3+4)+(2+3+4)+(1+3+4)+(1+2+4)+(3+4)+(1+2+3)+(2+4)+(2+3)
分析 用 f[i]表示价值为 i 的背包的不同种数，可以用 DP 求出： f[i] =∑ [i−w[j]] 然后从 ∑w[j] 开始从大到小枚举 f[i]，则这 f[i]种背包的总价值为 f[i]*i。枚举 直到人数已经大于等于 M 的为止，统计一下答案就可以了。
程序：
var i,j:longint; tj,ans,n,m:int64; a:array[0..600]of int64; f:array[0..25100]of int64; begin assign(input,'team.in'); reset(input); assign(output,'team.out'); rewrite(output); readln(m,n); tj:=0; for i:=1 to n do begin read(a[i]); tj:=tj+a[i]; end; f[0]:=1; for i:=1 to n do for j:=tj downto 0 do if j>=a[i] then f[j]:=f[j]+f[j-a[i]]; ans:=0; for i:=tj downto 0 do if f[i]<=m then begin m:=m-f[i]; ans:=ans+f[i]*i; end else begin ans:=ans+i*m; break; end; write(ans); close(input); close(output); end.