CATU2 - Cái túi 2
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Trong siêu thị có N gói hàng, gói hàng thứ i có trọng lượng là Wi và giá trị là Vi. 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 là M. Hỏi tên trộm sẽ lấy đi những gói hàng nào để được tổng giá trị là lớn nhất.

Dữ liệu nhập:

- Dòng thứ nhất là hai số N, M cách nhau một khoảng trắng (1 ≤ N ≤ 100, 1 ≤ M ≤ 100)

- Trong N dòng tiếp theo, dòng thứ i là hai số nguyên Wi và Vi cách nhau một khoảng trắng (1 ≤ Wi , Vi ≤ 100)

Dữ liệu xuất:

- Nếu tên trộm không thể lấy được món đồ nào, in ra 0.

- Nếu tên trộm có thể lấy được ít nhất một món đồ, dòng thứ nhất in ra giá trị lớn nhất tên trộm có thể lấy. Dòng thứ hai là chỉ số những gói bị lấy. Nếu có nhiều cách lấy đồ có cùng giá trị lớn nhất, chỉ cần in ra một cách bất kỳ.

Ví dụ

  • input
    5 11
    3 3
    4 4
    5 4
    9 10
    4 5
    output
    12
    5 2 1

Lấy 3 đồ vật 1, 2, 5 có tổng trọng là: 3+4+4 = 11 và tổng giá trị là: 3+4+5 = 12

Back to Top