02/10/2018, 14:02
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 ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 | 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. |
