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 n và w (n, w £ 1000).
• Dòng thứ hai ghi n số nguyên dương a_i (a_i < 1000, i = 1, 2, …, n).
• Dòng cuối cùng ghi n số nguyên dương c_i (c_i < 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ụ:

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ế