//
you're reading...
Bài tập huấn luyện, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi

Bài tập huấn luyện: Xếp ba lô

[Nội dung huấn luyện: Duyệt nhánh cận]


Chuyên đề  Duyệt nhánh cận – Bài 1


Đề bài


Một va ly có thể chứa tối ða W ðơn vị trọng lượng. Có N loại ðồ vật, số lượng mỗi loại không hạn chế. Loại ðồ vật thứ i có trọng lượng Ai và có giá trị Ci. Hỏi nên chọn những loại ðồ vật nào và số lượng bao nhiêu ðể xếp vào va ly sao cho:

– tổng trọng lượng của các vật không vượt quá giới hạn W của valy

– tổng giá trị của các vật là lớn nhất

Hướng dẫn


Gợi ý: Với mỗi loại ðồ vật i, gọi Ti là giá trị riêng của nó: Ti = Ci / Ai. Sau ðó sắp các loại ðồ
vật theo thứ tự giảm dần của Ti.

Phương pháp duyệt nhánh cận tại mỗi bước duyệt loại ðồ vật i, ta lấy k ðồ vật loại này, khi ðó ðiều kiện ðể duyệt tiếp loại ðồ vật i+1 (ðiều kiện nhánh cận) là:

– k*Ai <= w – s(i) + k*Ci + (w – k*Ai)*Ti+1 > smax

Trong ðó:

– w là trọng lượng mà valy có thể chứa thêm sau bước duyệt loại ðồ vật i-1.
– s(i) là tổng giá trị hiện ðang có của valy sau bước duyệt loại ðồ vật i-1.
– smax là tổng giá trị valy của một các xếp ðã tìm ðược nhưng chưa tối ưu. Có thể khởi tạo smax ban ðầu bằng 0.



Chương trình


[]

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ả

Danh mục

Tháng Mười Hai 2016
M T W T F S S
« Nov   Jan »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: