Bài toán cái túi và những ứng dụng xung quanh nó

Tôi làm sao để chọn đúng các đồ vật cho chiếc túi của tôi?

Bài toán Cái túi, Bài toán Xếp ba lô, Bài toán Knapsack,...là những tên gọi khác nhau mà chúng ta thường nghe đến, nhưng tất cả đều dùng để chỉ chung một bài toán tối ưu hóa tổ hợp, trong đó ta cần phải lựa chọn một số đồ vật để nhét vào một chiếc túi với tải trọng biết trước, sao cho tổng giá trị của các đồ vật nhét vào là lớn nhất có thể. Bài toán này đã được nghiên cứu trong hơn một thế kỷ, và nó là một trong những bài toán có ứng dụng vô cùng to lớn trong thực tế.

Có rất nhiều dạng khác nhau của bài toán cái túi mà tôi đã giới thiệu tới các bạn ở những chuyên đề trước. Những dạng tiêu biểu của bài toán này có thể kể đến là:

• Bài toán Knapsack với các giá trị số thực: Trọng lượng và giá trị của các món đồ là số thực. Bài toán này chỉ có thể giải quyết bằng phương pháp Quay lui (hoặc cải tiến bằng Nhánh cận).

• Bài toán Knapsack cho phép cắt nhỏ đồ vật (Fractional Knapsack): Các đồ vật được phép cắt ra và lấy một phần. Bài toán này có thể giải quyết bằng phương pháp Tham lam.

• Bài toán Knapsack 0−10 - 10−1: Các vật chỉ có thể chọn hoặc không chọn, ngoài ra giá trị và trọng lượng của các vật đều là số nguyên. Bài toán này có thể giải bằng phương pháp Quy hoạch động.

Trong bài viết này, chúng ta sẽ cùng tập trung nghiên cứu bài toán Knapsack 0−10 - 10−1 và một số ứng dụng của nó trong việc giải những bài toán Quy hoạch động có tư duy tương tự.

Phát biểu bài toán

Cho n vật khác nhau, vật thứ i i i có trọng lượng w i w_i w i ​ và giá trị v i v_i v i ​. Bạn mang theo một chiếc túi có tải trọng tối đa là W , W, W, nhiệm vụ của bạn là chọn ra các đồ vật để cho vào túi sao cho tổng giá trị của các đồ vật lấy được là lớn nhất có thể.

Input:

• Dòng đầu tiên chứa hai số nguyên dương n và W .
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương w i w_i w i ​ và v i v_i v i ​ phân tách nhau bởi dấu cách.

Output:

• Dòng đầu tiên in ra tổng giá trị lớn nhất của các vật lấy được.
• Dòng thứ hai in ra chỉ số của các vật được lựa chọn theo thứ tự tăng dần.

Sample Input:
3 50
10 60
20 100
30 120

Sample Output:
220
2 3

Ý tưởng

Gọi dp[i][j] là tổng giá trị lớn nhất của các đồ vật lấy được khi chọn trong các đồ vật từ 1 tới i i i và giới hạn tổng trọng lượng của chúng là j j j. Kết quả của bài toán là tổng giá trị lớn nhất chọn được trong n vật với giới hạn trọng lượng là W , W, W, sẽ chính là dp[n][W] .

Xét đồ vật thứ i , i, i, và giới hạn trọng lượng hiện tại là j , j, j , ta có hai phương án để lựa chọn:

• Nếu vật thứ i i i không được chọn vào phương án tối ưu, thì kết quả tối ưu sẽ được chọn trong (i−1) (i - 1) (i−1) đồ vật trước đó với giới hạn trọng lượng vẫn là j j j .
• Nếu vật thứ i i i được chọn vào phương án tối ưu, thì tải trọng còn lại có thể sử dụng là (j−wi) (j - w_i) (j−wi) cho (i−1) (i - 1) (i−1) đồ vật phía trước, và ta được thêm giá trị v i v_i v i ​ của vật thứ i . Dĩ nhiên, trường hợp này chỉ xét đến khi j≥wi j \geq w_i j≥wi .

Dễ thấy rằng, nếu như j

dp[i][j] = { dp[i-1][j]; for j < w_i, max(dp[i-1][j], dp[i][j-w_i] + v_i); for j >= w_i }

Cơ sở quy hoạch động dễ thấy là dp[0][j]=0, dp[0][j]=0, dp[0][j]=0, vì giá trị lớn nhất có thể chọn được trong số 0 đồ vật thì vẫn là 0.

Để truy vết lại các món đồ được chọn, ta sẽ đi ngược về trên bảng phương án, bắt đầu từ vị trí kết quả là dp[n][W] , dp[n][W], dp[n][W] (hàng n, n, n, cột W, W, W). Nếu như dp[n][W]=dp[n−1][W] , dp[n][W] = dp[n - 1][W], dp[n][W]=dp[n−1][W] tức là món đồ thứ n không được chọn, ta truy ngược về dp[n−1][W] , dp[n - 1][W], dp[n−1][W]. Ngược lại nếu dp[n][W]≠dp[n−1][W] , dp[n][W] \ne dp[n - 1][W], dp[n][W]​=dp[n−1][W] nghĩa là phương án lựa chọn tối ưu có chứa món đồ thứ n và truy ngược lên dp[n−1][W−w_n] , dp[n - 1][W - w_n], dp[n−1][W−w_n]. Tiếp tục như vậy cho tới khi đi về tới hàng 0 0 0 của bảng phương án (tức là cơ sở quy hoạch động) thì dừng lại.

Cài đặt

Ngôn ngữ C++:

#include  using namespace std;  void enter(int &n, int &W, vector> &items) {     cin >> n >> W;     items.resize(n + 1);      for (int i = 1; i <= n; ++i) {         cin >> items[i].first >> items[i].second;     } }  void trace_back(int n, int W, vector> &dp, vector> &items) {     vector picked_items;      while (n > 0) {         if (dp[n][W] == dp[n - 1][W]) {             --n;         } else {             picked_items.push_back(n);             W -= items[n].second;             --n;         }     }      for (int i = picked_items.size() - 1; i >= 0; --i) {         cout << picked_items[i] << ' ';     } }  void solution(int n, int W, vector> &items) {     vector> dp(n + 1, vector(W + 1, 0));      for (int i = 1; i <= n; ++i) {         for (int j = 0; j <= W; ++j) {             dp[i][j] = dp[i - 1][j];              if (j >= items[i].first) {                 dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i].first] + items[i].second);             }         }     }      cout << dp[n][W] << endl;     trace_back(n, W, dp, items); }  int main() {     int n, W;     vector> items;      enter(n, W, items);     solution(n, W, items);      return 0; }

Ngôn ngữ Python:

def enter(n, W, items):     n, W = map(int, input().split())     items = [(0, 0) for i in range(n + 1)]      for i in range(1, n + 1):         items[i] = map(int, input().split())  def trace_back(n, W, dp, items):     picked_items = []      while n > 0:         if dp[n][W] == dp[n - 1][W]:             n += 1         else:             picked_items.append(n)             W -= items[n][0]             n += 1      print(reverse(picked_items))  def solution(n, W, items):     dp = [[0] * (W + 1) for i in range(n + 1)]      for i in range(1, n + 1):         for j in range(0, W + 1):             dp[i][j] = dp[i - 1][j]              if j >= items[j][0]:                 dp[i][j] = max(dp[i][j], dp[i - 1][j - items[j][0]] + items[j][1])      print(dp[n][W])     trace_back(n, W, dp, items)  if __name__ == '__main__':     n, W = 0, 0     items = []      enter(n, W, items)     solution(n, W, items)

Các nguồn tham khảo:

• https://www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/
• http://www.or.deis.unibo.it/knapsack.html
• https://en.wikipedia.org/wiki/Knapsack_problem
• https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

©️ Tác giả: Vũ Quế Lâm từ Viblo