Giải bài toán xếp ba lô (bài toán cái túi) với C++

Bài toán xếp ba lô (còn được biết đến với tên gọi bài toán cái túi) 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. Các bài toán tương tự thường xuất hiện trong kinh doanh.

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 vấn đề đặt ra là tên 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?

Yêu cầu: Hãy xác định tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi được.

Dữ liệu: Vào từ tệp văn bản DRSEM.INP gồm:

• Dòng 1: Ghi số nguyên dương n và m (n ≤ 20, m ≤ 10⁹).
• Trong n dòng tiếp theo, dòng thứ i ghi số nguyên dương a_i và b_i (a_i, b_i ≤ 10⁹).

Dữ liệu vào đảm bảo có ít nhất một cách chọn đồ vật.

Kết quả: Ghi ra tệp văn bản DRSEM.OUT gồm một dòng duy nhất ghi tổng giá trị đồ vật lớn nhất mà tên trộm có thể mang đi được.

Code tham khảo:

#include <iostream>
using namespace std;
int max(int x, int y) {
   return (x > y) ? x : y;
}
int tromDo(long long m, int a[], int b[], int n) {
   int i, t;
   int k[n + 1][m + 1];
   for (i = 0; i <= n; i++) {
      for (t = 0; t <= m; t++) {
         if (i == 0 || t == 0)
            k[i][t] = 0;
         else if (b[i - 1] <= t)
            k[i][t] = max(a[i - 1] + k[i - 1][t - b[i - 1]], k[i - 1][t]);
         else
        k[i][t] = k[i - 1][t];
      }
   }
   return k[n][m];
}
int main() {
    freopen("DRSEM.INP","r",stdin);
    freopen("DRSEM.OUT","w",stdout);
    int n; long long m;
    cin >> n >> m;
    int a[n], b[n];
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      cin >> b[i];
    }
   cout << tromDo(m, a, b, n);
   return 0;
}