VCOWFLIX – spoj

Đề bài: http://vn.spoj.com/problems/VCOWFLIX/

Thuật toán:

• Gọi L[i][j] tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim khi có i con bò và sức chứa của xe là j.
  • Nếu a[i]<=j thì L[i,j]:=max(L[i-1,j], L[i-1,j-a[i]]+a[i]);
  • Nếu a[i]>j thì L[i,j]:=L[i-1,j];

Code:

• Pascal

uses    math;
const   fi='';
        fo='';
        maxn=16;
        oo=5000;
var     l:array[0..maxn,0..5000] of longint;
        a:array[1..maxn] of longint;
        i,j,c,n:longint;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);

        readln(c,n);
        for i:=1 to n do read(a[i]);

        for i:=1 to n do
                for j:=0 to c do
                        begin
                            l[i,j]:=l[i-1,j];
                            if a[i]<=j then
                                l[i,j]:=max(l[i,j],l[i-1,j-a[i]]+a[i]);
                        end;

        writeln(l[n,c]);

        close(input);close(output);
end.