//
you're reading...
00 - Chủ đề chung

Bài tập huấn luyện: Xếp va li (A)


Đề bài


Cho một va ly có thể chứa W đơn vị trọng lượng. Có N loại đồ vật (số lượng mỗi đồ vật không hạn chế), đồ vật i có trọng lượng A[i]  và có giá trị là C[i]. Hỏi nên chọn mỗi loại đồ vật bao nhiêu xếp vào va ly để tổng giá trị  của va ly là lớn  nhất.

Dữ liệu vào lấy từ file văn bản ‘VALY.INP’ gồm ba dòng

  • Dòng thứ nhất là N và W
  • N dòng tiếp theo: dòng i+1 ghi hai số: A[i] và C[i] (i=1,2,..N), hai số cách nhau bởi dấu cách.

Kết quả ghi ra file văn bản ‘VALY.OUT’ theo quy cách sau:

  • Dòng thứ nhất là tổng giá trị lớn nhất của va ly
  • Các dòng tiếp theo mỗi dòng 2 số: số i (số hiệu vật được chọn) và số x (số lượng chọn vật i)

Ví dụ:

VALY.INP VALY.OUT
4 100 110
50 50 2   1
19 20 3   1
80 90
21 25

Lời giải


uses crt;
const fi = ‘valy.in3’;
fo = ‘valy.ou3’;
var
a, {Träng l­îng vËt i : a[i]}
c, {Gi¸ trÞ vËt i : c[i]}
w, {Träng l­îng tèi ®a cña va ly}
n : longint; {Sè ®å vËt}
sum_max : longint; {Tæng gi¸ trÞ chän ®­îc}
g1,g2:array[0..1500] of integer; {Theo râi tæng gi¸ trÞ chän}
v1,v2:array[0..10000] of integer; {Sè hiÖu vËt chän}
x : array[1..1500] of integer;{x[i]: Sè l­îng vËt i ®­îc chän}

procedure input;
var f : text;
i : integer;
begin
assign(f,fi);
reset(f);
readln(f,n,w);
for i:=1 to n do
read(f,a[i],c[i]);
close(f);
end;
function max(a,b:longint):longint;
begin
if a>=b then max:=a
else max:=b;
end;
procedure tinh2(k,y:integer);{k=2,4,6,..-> t¹o g2 tõ g1, v2 tõ v1}
begin
if a[k]>y then
g2[y]:=g1[y] {kh«ng chän vËt k, g2 lÊy l¹i gi¸ trÞ g1}
else
g2[y]:=max(c[k]+g2[y-a[k]], g1[y]);{cã thÓ chän k, hoÆc kh«ng}
if g1[y]=g2[y] then {kh«ng chän vËt k}
v2[y]:=v1[y]; {ghi l¹i vËt chän ë b­íc tr­íc}
if g1[y]<g2[y] then {chän vËt k} v2[y]:=k; {ghi l¹i vËt võa chän lµ k} end; procedure tinh1(k,y:integer);{k =3,5,7..-> t¹o g1 tõ g2, v1 tõ v2}
begin {qu¸ tr×nh t­¬ng tù thñ tôc trªn}
if a[k]>y then g1[y]:=g2[y]
else
g1[y]:=max(g2[y],c[k]+g1[y-a[k]]);
if g2[y]=g1[y] then v1[y]:=v2[y];
if g2[y]<g1[y] then v1[y]:=k; end; procedure qhd; var i,k,y,cs,s,j:integer; begin (* Khëi t¹o *) g1[0] := 0; g2[0] := 0; v1[0] := 0; v2[0] := 0; for i:=1 to w do {c¸c kh¶ n¨ng vÒ träng l­îng cßn thiÕu cña va ly} begin g1[i] := c[1]*(i div a[1]); if g1[i] >0 then
v1[i] := 1{chän vËt 1, sè l­îng lµ i div a[1]}
else v1[i]:=0;
end;
for k:=2 to n do {XÐt chän c¸c vËt tõ 2->n}
begin
if (k mod 2)=0 then
for y:=1 to w do tinh2(k,y)
{Khi va ly cßn thiÕu träng l­îng y, xÐt chän vËt k ch½n, x©y dùng g2,v2}
else
for y:=1 to w do tinh1(k,y);
{Khi va ly cßn thiÕu träng l­îng y, xÐt chän vËt k lÎ, x©y dùng g1,v1}
end;
(* T×m ng­îc: t×m ph­¬ng ¸n tèi ­u *)
for i:=1 to n do x[i]:=0;
s:=w;
if (n mod 2)=0 then {NÕu n ch½n th× dùa vµo g2,v2}
begin
repeat
j := v2[s];
x[j] := x[j]+1;
s := s-a[j];
until v2[s]=0;
sum_max:=g2[w];
end
else {NÕu n lÎ th× dùa vµo g1,v1}
begin
repeat
j := v1[s];
x[j] := x[j]+1;
s := s-a[j];
until v2[s]=0;
sum_max:=g1[w];
end
end;
procedure inkq;
var i : integer;
f : text;
begin
assign(f,fo);
rewrite(f);
for i:=1 to n do
if x[i]>0 then
writeln(f,i:4,{a[i]:4,c[i]:4,}x[i]:4);
writeln(f,sum_max);
close(f);
end;
BEGIN
clrscr;
input;
qhd;
inkq;
END.


Tham khảo


Trường hợp số lượng đồ vật hạn chế

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: