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

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


Đề bài


(Xếp va li, mỗi đồ vật chỉ có một cái)
Cho một va ly có thể chứa W đơn vị trọng lượng. Có N đồ vật, đồ vật i có trọng lượng A[i] và có giá trị là C[i]. Hãy xếp đồ vật vào va ly để tổng giá trị của va ly là tốt 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ố 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 các đồ vật được chọn
ã Các dòng tiếp theo mỗi dòng 3 số là số hiệu, trọng lượng, giá trị vật được chọn
Ví dụ:
VALY.INP
3 10
1 70
5 300
5 300

VALY.OUT
600
2 5 300
3 5 300
Hướng dẫn:

Bài xếp va ly b) khác bài xếp va ly a) ở chỗ mỗi loại đồ vật chỉ có 1 cái. Có thể giải như sau:
a) Tổ chức dữ liệu: Mảng hai chiều L(N,W): L[i,j] là giá trị của va ly khi trọng lượng max của va ly là j và xét xong từ vật 1 đến vật i.
b) Khởi trị L[0,j]=0; j: 0<j<=w, L[i,0]=0; i: 0<i<=N
c) Xây dựng nhãn L[i,j] theo công thức
L[i,j] = Max(L[i-1,j], L[i-1,j-A[i]] + C[i]) nếu A[i]j
Hoặc L[i,j] = L[i-1,j] nếu A[i]>j


Lời giải


uses   crt;

const  maxn = 100;

maxw = 1000;

fi   = ‘valy.in2’;

fo   = ‘valy.ou2’;

type   m1   = array[0..maxw] of word;

m2   = array[0..maxn] of ^m1;

var    L    : m2;

a,c  : array[1..maxn] of word;

n,w  : word;

procedure doc_file;

var f : text; i : word;

begin

assign(f,fi); reset(f);

readln(f,n,w);

fillchar(a,sizeof(a),0);

c := a;

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

close(f);

end;

function  max(v1,v2 : word): word;

begin

if v1>v2 then v2 := v1;

max := v2;

end;

procedure xuly;

var  i,j : word ;

begin

for i:=0 to n do

begin

new(L[i]);

for j:=0 to w do

L[i]^[j] := 0;

end;

for i:=1 to n do

for j:=1 to w do

begin

if a[i]<=j then

L[i]^[j]:=

max(L[i-1]^[j-[i]]+c[i],L[i]^[j])

else L[i]^[j] := L[i-1]^[j];

end;

end;

procedure ghi_file;

var vmax,v0,n0,i,j : word;

f : text;

begin

assign(f,fo);  rewrite(f);

vmax  := 0; v0    := 0; n0    := 0;

for j:=1 to w do

if vmax<L[n]^[j] then

begin

vmax := L[n]^[j];

v0   := j;

end;

j := v0;

writeln(f,vmax);

for i:=n downto 1 do

if L[i]^[j]<>L[i-1]^[j] then

begin

inc(n0);

writeln(f,i,’ ‘,a[i],’ ‘,c[i]);

j := j – a[i];

end;

close(f);

end;

BEGIN

doc_file;

xuly;

ghi_file;

END.

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: