Bài 2. Alibaba và 40 tên cướp (TS10 Đắk Lắk 2021)
Xem PDFTrong một chuyến đi tìm kho báu, Alibaba đã lạc vào một hang động đầy vàng bạc, châu báu của 40 tên cướp. Trong hang động có \(n\) hòn đá quý, hòn đá thứ \(i\) có trọng lượng là \(w_i\) và giá trị là \(v_i\). Alibaba mang theo một chiếc túi có thể chứa được trọng lượng tối đa là \(M\).
Yêu cầu: Hãy giúp Alibaba chọn các hòn đá quý để cho vào túi sao cho tổng giá trị của chúng là lớn nhất và tổng trọng lượng không vượt quá \(M\).
Input
- Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(M\) (\(n \le 100, M \le 10^4\)).
- \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(w_i\) và \(v_i\) (\(w_i, v_i \le 10^4\)).
Output
- Một số nguyên duy nhất là tổng giá trị lớn nhất của các hòn đá quý mà Alibaba có thể chọn.
Example
Test 1
Input
3 4
1 4
2 5
3 8Output
9Note
Alibaba chọn hòn đá thứ nhất (\(w_1=1, v_1=4\)) và hòn đá thứ ba (\(w_3=3, v_3=8\)). Tổng trọng lượng là \(1+3=4 \le 4\), tổng giá trị là \(4+8=12\).
Đính chính ví dụ từ hình ảnh: Trong hình ảnh minh họa, với \(n=3, M=4\) và các vật \((1, 4), (2, 5), (3, 8)\), nếu chọn vật 1 và 3 thì tổng giá trị là \(12\). Nếu chọn vật 2 và 1 thì tổng giá trị là \(9\). Tuy nhiên, kết quả mẫu trong hình ghi là \(9\) có thể do một bộ test khác hoặc cách giải thích khác. Dựa trên yêu cầu bài toán cái túi (Knapsack), giá trị lớn nhất phải là \(12\). Tuy nhiên, để bám sát hình ảnh đề bài cung cấp:
- Nếu chọn vật 1 và 2: \(w = 1+2=3 \le 4, v = 4+5=9\).
- Nếu chọn vật 3 và 1: \(w = 3+1=4 \le 4, v = 8+4=12\).
- Nếu chọn vật 3: \(w = 3 \le 4, v = 8\).
Kết quả \(9\) trong ảnh có thể tương ứng với bộ dữ liệu khác hoặc ràng buộc mỗi vật chỉ chọn 1 lần và có sự nhầm lẫn trong hình ảnh ví dụ. Theo đúng thuật toán Knapsack 0/1 cho test trên, kết quả là \(12\).
Scoring
- Subtask \(1\) (\(60\%\) số điểm): \(n \le 20, M \le 100\).
- Subtask \(2\) (\(40\%\) số điểm): \(n \le 100, M \le 10^4\).
Bình luận (1)