tailieunhanh - Bài toán xếp ba lô

Bài toán xếp ba lô (một số sách ghi là bài toán cái túi, tương tự như bài toán xếp vali) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Một số cách phát biểu nội dung bài toán: Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ. | Bài toán xếp ba lô Bài toán xếp ba lô một số sách ghi là bài toán cái túi tương tự như bài toán xếp vali là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi với giới hạn khối lượng để mang theo trong một chuyến đi. Một số cách phát biểu nội dung bài toán Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được. Một hành khách chỉ được mang theo một vali có khối lượng hàng hoá tối đa là M. Hành khách đó đã chuẩn bị ra N dồ vật được đánh số từ 1 đến N để chuẩn bị mang theo. Đồ vật thứ i có trọng lượng là ai và giá trị sử dụng là ci i 1 2 . N Yêu cầu Chỉ ra đồ vật mà hành khách đó cần mang theo sao cho tổng giá trị sử dụng là lớn nhất Bài toán Trong siêu thị có n gói hàng n 100 gói hàng thứ i có trọng lượng là Wi 100 và trị giá Vi 100. Một tên trộm đột nhập vào siêu thị tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M M 100 . Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị lớn nhất. Input file văn bản Dòng 1 Chứa hai số n M cách nhau ít nhất một dấu cách n dòng tiếp theo dòng thứ i chứa hai số nguyên dương Wi Vi cách nhau ít nhất một dấu cách Output file văn bản BAG. OUT Dòng 1 Ghi giá trị lớn nhất tên trộm có thể lấy Dòng 2 Ghi chỉ số những gói bị lấy 5 11 11 3 3 4 4 5 4 9 10 4 4 5 2 1 Cách giải Nếu gọi F i j là giá trị lớn nhất có thể có bằng cách chọn trong các gói 1 2 . i với giới hạn trọng lượng j. Thì giá trị lớn nhất khi được chọn trong số n gói với giới hạn trọng lượng M chính là F n M . 1. Công thức truy hồi tính F i j . Với giới hạn trọng lượng j việc chọn tối ưu trong số các gói 1 2 . i - 1 i để có giá trị lớn nhất sẽ có hai khả năng Nếu không chọn gói thứ i thì F i j là giá trị .