//
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ế

 

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Một 2016
H B T N S B C
« Th10   Th12 »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Thống kê

  • 206,489 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: