Chọn đồ vật

 Chọn HSG lớp 12 - Bạc Liêu 2012 - Bảng A - Ngày 2 - Bài 3/3
Cho n đồ vật. Trọng lượng và giá trị của vật i lần lượt là A[i], B[i]. Hãy chọn ra một số vật sao cho tổng trọng lượng của chúng không vượt quá trọng lượng M cho trước và tổng giá trị là lớn nhất. Cho biết 0 < n <= 20;  0 < M <= 100; 0 < A[i], B[i] < 256
Dữ liệu vào: Cho trong file NHAP.INP gồm n + 1 dòng:
- Dòng đầu là 2 số n, M;
- Dòng i + 1 (1 <= i <= n) ghi 2 số nguyên dương A[i], B[i].
Dữ liệu ra: Ghi vào file XUAT.OUT gồm:
- Mỗi dòng ghi 3 số: i, A[i], B[i];
- Dòng cuối là 3 số: Tổng số vật, tổng trọng lượng và tổng giá trị của các vật được chọn. Các số ghi trên cùng một dòng được cách ít nhất một dấu cách.
Ví dụ:
   NHAP.INP
      5 100
      42 40
      30 72
      40 6
      25 48
      13 3
   XUAT.OUT
      4 25 48
      2 30 72
      1 42 40
      3 97 160

                                                           Lời giải tham khảo