(ssl 2291)パケットバックパック

リュックサックを組む
Time Limit:10000MS  Memory Limit:65536K Total Submit:65 Accepted:47  Case Time Limit:1000MS
Description
N個の品物とV容量のリュックサックがあります.i番目の品物の費用はc[i]、価値はw[i]です.これらのアイテムはいくつかのグループに分けられ、各グループのアイテムは互いに衝突し、最大1つを選択します.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
Input
第1行:3つの整数、v(リュックサック容量、v<=200)、n(物品数、n<=30)、t(最大グループ番号、t<=10)、第2.n+1行:各行の3つの整数wi、ci、pは、各物品の重量、価値、所属グループ番号を表す.
Output
1行のみ、1つの数で、最大の総価値を表します.
Sample Input

10 6 3
2 1 1
3 3 1
4 8 2
6 9 2 
2 8 3
3 9 3

Sample Output

20

Source

var
 c,w,f:array[0..1000]of longint;
 a:array[0..100,0..100]of longint;
 n,v,t,g,i,j,k:longint;
function max(a,b:longint):longint;
begin
 if a>b then exit(a);
 exit(b);
end;
begin
 readln(v,n,t);
 for i:=1 to n do
  begin
   readln(w[i],c[i],g);
   inc(a[g,0]);//      +1
   a[g,a[g,0]]:=i;
  end;
 for i:=1 to t do//        =   t 
  for j:=v downto 0 do
   for k:=1 to a[i,0] do
    if j>=w[a[i,k]] then
     f[j]:=max(f[j],f[j-w[a[i,k]]]+c[a[i,k]]);
 writeln(f[v]);
end.