Lựa quà sinh nhật.

by Admin Thu Dec 08, 2022 4:00 pm

Bài 7: Lựa quà sinh nhật.

Tháng 13 là sinh nhật của Ninh, thầy Đoài muốn tặng thật nhiều quà cho bạn, vì vậy thầy dẫn Ninh đến “Điện máy xanh ở thị trấn PP” để mua quà tặng. Trong siêu thị có n món hàng (n<=10^4), món hàng thứ i có trọng lượng W (W<=100) và có giá trị V[i] (V[i] <=100). Thầy cho Ninh lấy thoải mái các sản phẩm, miễn sao vác nổi tất cả sản phẩm đó ra khỏi siêu thị ([/i][/i]

var fi,fo:text;
w,v:array[0..100000]of longint;
n,m,i,kl,gt,ln:longint;
s,kt,kq:string;

procedure np;
var i:longint;
begin
for i:=n downto 1 do
if s[i]='0' then begin s[i]:='1'; break; end else s[i]:='0';
end;
begin
assign(fi,'SINHNHAT.INP'); assign(fo,'SINHNHAT.OUT');
reset(fi); readln(fi,n,m);
for i:=1 to n do readln(fi,w[i],v[i]);
for i:=1 to n do begin s:=s+'0'; kt:=kt+'1'; end;
while s<>kt do
begin
kl:=0; gt:=0; np;
for i:=1 to n do
if s[i]='1' then begin kl:=kl+w[i]; gt:=gt+v[i]; end;
if kl<=m then if gt>ln then begin ln:=gt; kq:=s; end;
end;
rewrite(fo); writeln(fo,ln);
for i:=n downto 1 do
if kq[i]='1' then write(fo,i,' ');
close(fi); close(fo);
end.