BCCOW spoj PTIT – Đi xem phim

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCCOW/

1. Đề bài BCCOW spoj PTIT

Nông dân John đang đưa các con bò của anh ta đi xem phim! Xe tải của anh ta thì có sức chứa có hạn thôi, là C (100 <= C <= 5000) kg,

anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối lượng của đống bò này là lớn nhất, đồng thời xe tải của anh ta vẫn chịu được.

Cho N (1 <= N <= 16) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu.

Dữ liệu

• Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N
• Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên: W_i

Kết quả

• Dòng 1: Một số nguyên là tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim.

Ví dụ:

Dữ liệu:

259 5

81

58

42

33

61

Kết quả:

242

Giải thích: 81+58+42+61 = 242; đây là tổng khối lượng bò lớn nhất có thể được.

2. Hướng dẫn BCCOW spoj PTIT

– bài này các bạn có thể dùng tham lam.

3. code tham khảo BCCOW spoj PTIT

const   fi='';
var
        A:array[1..16] of word;
        N:byte;
        M:word;
        f:text;
        dd:array[1..16] of boolean;
        S,smax:integer;
        sl:byte;

procedure docfile;
var     i:byte;
begin
        assign(f,fi); reset(f);
        readln(f,m,n);
        i:=0;
        while not eoln(f) do
                begin
                        inc(i);
                        readln(f,a[i]);
                        if a[i]>M then
                                begin
                                        dec(i);
                                        dec(n);
                                end;

                end;
        close(f);
end;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]>x do
            inc(i);
           while x>a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure init;
begin
        s:=0;
        smax:=0;
        sl:=0;
end;

procedure try; // chon con bo thu i;
var     j:byte;
begin
        if s>smax then
                smax:=s;
        for j:=1 to n do
                if (not dd[j]) and (s+a[j]<=m) then
                        begin

                                dd[j]:=true;
                                inc(s,a[j]);
                                try;
                                dd[j]:=false;
                                dec(s,a[j]);
                        end;
end;

begin
        docfile;
        sort(1,n);
        try;
        writeln(smax);
end.