//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Đề ôn luyện thi học kỳ

Bài tập huấn luyện:BÀI TOÁN CÁI BA LÔ (Túi xách)


Đề bài


Một người đi du lịch có n loại đồ vật có trọng lượng và giá trị khác nhau. Nhưng anh ta chỉ có một túi xách có dung lượng w (có thể chứa được một số đồ vật sao cho tổng trọng lượng của các đồ vật này nhỏ hơn hoặc đúng bằng w).

Bạn hãy viết chương trình giúp người đi du lịch phải chọn lựa một danh sách các đồ vật mang đi như thế nào để tổng giá trị đồ vật mang đi là lớn nhất. Giả thiết mỗi loại đồ vật có đủ nhiều.

Dữ liệu vào: File vào gồm 3 dòng:

  • Dòng đầu tiên của file vào chứa hai số nguyên dương nw (n, w £ 1000).
  • Dòng thứ hai ghi n số nguyên dương ai (ai < 1000, i = 1, 2, …, n).
  • Dòng cuối cùng ghi n số nguyên dương ci (ci < 100.000, i = 1, 2, …, n). Các số trên một dòng cách nhau bởi một dấu cách.

Kết quả: File ra gồm 2 dòng:

Dòng thứ nhất ghi tổng giá trị đồ vật mang đi lớn nhất.

Dòng thứ hai ghi n số nguyên cách nhau bởi dấu cách, trong đó số thứ i là số lượng đồ vật i cần mang theo (i = 1, 2, …, n). Nếu có nhiều cách mang đồ vật đều cho tổng giá trị lớn nhất thì ghi ra một cách bất kỳ trong chúng.

Ví dụ:

TUIXACH.INP  TUIXACH.OUT
5 20 56
1 2 3 4 6 2 0 6 0 0
1 2 9 8 16

Hướng dẫn


[Chương trình mẫu]

  1. Tham khảo lời giải
  2. Xếp va li (A) – Trường hợp số lượng đồ vật không hạn chế
  3. Xếp va li (B) – 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: