Bài toán cái túi và những ứng dụng xung quanh nó
I. Bài toán Cái túi và những bài toán áp dụng
1. Lời mở đầu
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 : 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 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ự.
2. Phát biểu bài toán
Cho đồ vật khác nhau, đồ vật thứ có trọng lượng và giá trị . Bạn mang theo một chiếc túi có tải trọng tối đa là 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 và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và 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
3. Ý tưởng
Gọi 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ừ tới và giới hạn tổng trọng lượng của chúng là . Kết quả của bài toán là tổng giá trị lớn nhất chọn được trong vật với giới hạn trọng lượng là sẽ chính là .
Xét đồ vật thứ và giới hạn trọng lượng hiện tại là ta có hai phương án để lựa chọn:
- Nếu vật thứ 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 đồ vật trước đó với giới hạn trọng lượng vẫn là .
- Nếu vật thứ đượ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à cho đồ vật phía trước, và ta được thêm giá trị của vật thứ . Dĩ nhiên, trường hợp này chỉ xét đến khi .
Dễ thấy rằng, nếu như thì chỉ có duy nhất cách lựa chọn đầu tiên, còn nếu thì có thể lựa chọn theo cả hai cách để lấy cách tốt hơn. Tổng hợp lại, ta có công thức quy hoạch động:
Cơ sở quy hoạch động dễ thấy là vì giá trị lớn nhất có thể chọn được trong số đồ vật thì vẫn là .
Để 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à (hàng cột ). Nếu như tức là món đồ thứ không được chọn, ta truy ngược về . Ngược lại nếu nghĩa là phương án lựa chọn tối ưu có chứa món đồ thứ và truy ngược lên . Tiếp tục như vậy cho tới khi đi về tới hàng của bảng phương án (tức là cơ sở quy hoạch động) thì dừng lại.
4. Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
void enter(int &n, int &W, vector < pair < int, int > > items)
{
cin >> n >> W;
items.resize(n + 1);
// Sử dụng kiểu pair để nhập dữ liệu các món đồ.
// items[i].first và items[i].second lần lượt là trọng lượng và giá trị của đồ vật thứ i.
for (int i = 1; i <= n; ++i)
cin >> items[i].first >> items[i].second;
}
// Truy vết các món đồ được chọn.
void trace_back(int n, int W, vector < vector < int > > &dp, vector < pair < int, int > > &items)
{
vector < int > 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] << ' ';
}
// Quy hoạch động.
void solution(int n, int W, vector < pair < int, int > > &items)
{
vector < vector < int > > dp(n + 1, vector < int >(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);
}
// In kết quả.
cout << dp[n][W] << endl;
trace_back(n, W, dp, items);
}
main()
{
int n, W;
vector < pair < int, int > > items;
enter(n, W, items);
solution(n, W, items);
}
Ngôn ngữ Python:
def enter(n, W, items):
n, W = map(int, input().split())
items = [(0, 0) for _ 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 _ 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)
II. Một số bài toán ứng dụng
1. Bài toán Cái túi vô hạn
Đề bài
Một tên trộm mang theo một chiếc túi có tải trọng vào trong một tiệm đá quý. Trong tiệm có loại đá quý, loại thứ có khối lượng và giá trị với số lượng viên đá mỗi loại là không giới hạn. Tên trộm cần chọn ra một số viên đá quý để mang theo sao cho tổng giá trị của chúng là lớn nhất có thể.
Xác định tổng giá trị đá quý lớn nhất mà tên trộm có thể mang theo với chiếc túi tải trọng
Input:
- Dòng đầu tiên chứa hai số nguyên dương và .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và 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 viên đá quý mà tên trộm lấy được.
- Dòng thứ hai in ra số nguyên với là số lần được chọn của viên đá quý thứ .
Sample Input:
2 100
1 1
50 30
Sample Output:
100
100 0
Explanation:
Có rất nhiều cách để tên trộm mang theo các viên đá quý:
- Mang theo viên có khối lượng tổng giá trị là .
- Mang theo viên có khối lượng tổng giá trị là .
- Mang theo viên có khối lượng và viên có khối lượng tổng giá trị là .
Vậy ta chọn phương án thứ .
Ý tưởng
Khác với bài toán cái túi bản gốc, ở bài toán này chúng ta được phép chọn một đồ vật nhiều lần. Nghĩa là ở mọi thời điểm lựa chọn, tất cả các đồ vật đều có thể được sử dụng.
Vì thế, ta chỉ cần sử dụng mảng một chiều với ý nghĩa là tổng giá trị đá quý lớn nhất thu được với giới hạn tải trọng là thay vì mảng hai chiều như bài toán gốc. Xét giới hạn tải trọng và viên đá quý có khối lượng giá trị . Nếu như thì ta lại có thể lựa chọn viên đá này vào tập các viên đá được chọn. Từ đó hình thành công thức:
Kết quả cuối cùng tất nhiên là .
Để truy vết, ta sử dụng một mảng là số lần được chọn của viên đá quý thứ . Bắt đầu từ vị trí trên bảng phương án. Duyệt qua từng viên đá quý, nếu như tới viên thứ mà thì viên đá thứ được chọn lần, cập nhật tăng vị trí thêm và truy ngược về vị trí trên bảng phương án. Cứ làm như vậy cho tới khi thì dừng lại.
Ta sẽ thu được giải thuật có độ phức tạp .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
void enter(int &n, int &W, vector < pair < int, int > > gems)
{
cin >> n >> W;
gems.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> gems[i].first >> gems[i].second;
}
void trace_back(int n, int W, vector < int > &dp, vector < pair < int, int > > &gems)
{
vector < int > chosen_times(n + 1, 0);
while (W != 0)
{
for (int i = 1; i <= n; ++i)
if (dp[W] == dp[W - gems[i].first] + gems[i].second)
{
W -= gems[i].first;
++chosen_times[i];
break;
}
}
for (int e: chosen_times)
cout << e << ' ';
}
void solution(int n, int W, vector < pair < int, int > > gems)
{
vector < int > dp(W + 1, 0);
for (int i = 0; i <= W; ++i)
for (int j = 1; j <= n; ++j)
if (i >= gems[j].first)
dp[i] = max(dp[i], dp[i - gems[j].first] + gems[j].second);
cout << dp[W] << endl;
trace_back(n, W, dp, gems);
}
main()
{
int n, W;
vector < pair < int, int > > gems;
enter(n, W, gems);
solution(n, W, gems);
}
Ngôn ngữ Python:
def enter(n, W, gems):
n, W = map(int, input().split())
gems = [(0, 0) for i in range(n + 1)]
for i in range(1, n + 1):
gems[i] = map(int, input().split())
def trace_back(n, W, dp, gems):
chosen_times = [0 for i in range(n + 1)]
while W != 0:
for i in range(1, n + 1):
if dp[W] == dp[W - gems[i][0]] + gems[i][1]:
W -= gems[i][0]
chosen_times[i] += 1
break
print(chosen_times)
def solution(n, W, gems):
dp = [0 for i in (W + 1)]
for i in range(W + 1):
for j in range(1, n + 1):
if i >= gems[j][0]:
dp[i] = max(dp[i], dp[i - gems[i][0]] + gems[i][1])
print(dp[W])
trace_back(n, W, dp, gems)
if __name__ == '__main__':
n, W = 0, 0
gems = []
enter(n, W, gems)
solution(n, W, gems)
2. Dãy con tổng bằng K
Đề bài
Cho một dãy số gồm phần tử nguyên và một số nguyên . Hãy đếm số dãy con không liên tiếp của dãy có tổng đúng bằng
Input:
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên phân tách nhau bởi dấu cách .
Output:
- Số nguyên duy nhất là số lượng dãy con có tổng bằng . Kết quả có thể rất lớn, nên hãy in ra phần dư của kết quả sau khi chia cho .
Sample Input:
4 6
1 2 3 3
Sample Output:
3
Ý tưởng
Dễ nhận thấy, có tổng cộng dãy con, nên phương pháp quay lui duyệt mọi dãy con là hoàn toàn không khả thi.
Ý tưởng ở đây là sử dụng quy hoạch động với tư duy giống như bài toán cái túi. Gọi là số lượng dãy con chọn ra trong mảng con có tổng là . Khi xét tới phần tử ta có thể:
- Không chọn vào dãy con, khi đó tổng số dãy con tạo ra sẽ là từ mảng con với tổng là số lượng là . Trường hợp này có thể xảy ra với cả hay .
- Chọn vào dãy con, khi đó ta còn lại tổng bằng phải tạo ra từ mảng con số dãy con tạo ra cũng sẽ tương ứng là . Dễ thấy trường hợp này chỉ xảy ra nếu như .
Vậy ta có công thức truy hồi:
Kết quả cuối cùng sẽ là .
Cơ sở quy hoạch động như sau: vì luôn luôn có một dãy con rỗng tổng bằng chọn trong mảng con . Tất nhiên, cũng bằng .
Độ phức tạp giải thuật: .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
void enter(int &n, int &K, vector < int > &a)
{
cin >> n >> K;
a.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
}
void solution(int n, int K, vector < int > &a)
{
vector < vector < long long > > dp(n + 1, vector < long long > (K + 1, 0));
for (int i = 0; i <= n; ++i)
dp[i][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= K; ++j)
{
dp[i][j] = dp[i - 1][j];
if (j >= a[i])
(dp[i][j] += dp[i - 1][j - a[i]]) %= mod;
}
cout << dp[n][K];
}
main()
{
int n, K;
vector < int > a;
enter(n, K, a);
solution(n, K, a);
}
Ngôn ngữ Python:
def solution(n, K, a):
mod = 10 ** 9 + 7
dp = [[0] * (K + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n + 1):
for j in range(1, K + 1):
dp[i][j] = dp[i - 1][j]
if j >= a[i]:
dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % mod
print(dp[n][K])
if __name__ == '__main__':
n, K = map(int, input().split())
a = [0 for i in range(n + 1)]
for i in range(1, n + 1):
a[i] = int(input())
solution(n, K, a)
III. Tài liệu 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
All Rights Reserved