POJ 1276(多重背包）

RT

count 表示 第i种面额在f[j] 放的数量

Program P1276;const   maxn=20;   maxcash=1000000;var   cash,n,i,j:longint;   cost,d:array[1..maxn] of longint;   f,count:array[0..maxcash] of longint;begin   while not seekeof do   begin      read(cash,n);      for i:=1 to n do read(d[i],cost[i]);      fillchar(f,sizeof(f),0);      for i:=1 to n do      begin         fillchar(count,sizeof(count),0);         for j:=cost[i] to cash do         begin            if (f[j]<f[j-cost[i]]+cost[i]) and (count[j-cost[i]]<d[i]) then            begin               f[j]:=f[j-cost[i]]+cost[i];               count[j]:=count[j-cost[i]]+1;            end;         end;      end;      writeln(f[cash]);   end;end.