¶ Quy hoạch động cái túi (DP Knapsack), phần 1
Tác giả:
- Nguyễn Tấn Minh - Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM.
Reviewer:
- Nguyễn Quang Minh - Michigan State University.
- Võ Khắc Triệu - National University of Singapore.
- Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành, Quãng Ngãi.
- Nguyễn Minh Hiển - Trường Đại học Công nghệ, ĐHQGHN.
¶ Giới thiệu
Quy hoạch động cái túi hay DP Knapsack là thuật ngữ dùng để gọi chung các thuật toán dùng để xử lý lớp bài toán cái túi (knapsack problem), chủ yếu tập trung vào việc xử lý hai dạng bài toán sau:
- 0/1 Knapsack Problem: Cho món đồ và một giới hạn , mỗi món đồ được gán trọng số và giá trị. Tìm một tập con các món đồ sao cho tổng trọng số không quá và tổng giá trị được cực đại hóa.
- Subset sum: Cho món đồ và một số nguyên , mỗi món đồ được gán trọng số. Kiểm tra sự tồn tại hoặc đếm số tập con các món đồ có tổng giá trị .
Tùy vào yêu cầu và giới hạn các tham số của từng bài toán, ta có rất nhiều lời giải khác nhau. Trong bài viết này, mình sẽ giới thiệu đến các bạn đọc một vài thuật toán quy hoạch động cái túi tiêu biểu cũng như ứng dụng của chúng trong các bài toán Lập trình thi đấu thực tế.
Trong cả 2 phần của bài viết này, ta sẽ giả sử rằng trọng số và giá trị của các món đồ đều là số nguyên.
¶ Bài toán 0/1 Knapsack
Để bắt đầu, chúng ta cùng tìm hiểu thuật toán quy hoạch động cái túi mà gần như lập trình viên nào cũng được tìm hiểu khi bắt đầu nghiên cứu các thuật toán quy hoạch động cơ bản.
¶ Bài toán
¶ Đề bài
Cho món đồ và một giới hạn , mỗi món đồ được gán trọng số và giá trị . Tìm một tập con các món đồ sao cho tổng trọng số không quá và tổng giá trị được cực đại hóa.
Nói cách khác, tìm sao cho và được cực đại hóa.
¶ Giới hạn
¶ Xây dựng trạng thái quy hoạch động
Để xây dựng trạng thái quy hoạch động cho bài toán trên, ta xác định tham số cần quan tâm như sau:
- Tham số chia để trị: Phạm vi bài toán con hay số món đồ đầu tiên đang xét.
- Tổng trọng số của tập con.
- Tổng giá trị của tập con.
Với giới hạn của bài toán, ta chọn hai tham số đầu tiên để đặt trạng thái và tham số còn lại làm giá trị cần tính. Cụ thể, định nghĩa là tổng giá trị tối đa của một tập con có tổng trọng số nếu chỉ xét món đồ đầu tiên.
¶ Xây dựng công thức truy hồi & trường hợp cơ sở
Để tính , ta tìm cách rút gọn về bài toán con chỉ xét món đồ đầu tiên rồi xét riêng việc chọn hay không chọn món đồ thứ . Cụ thể:
- Nếu món đồ thứ được chọn, nghĩa là tổng trọng số sẽ được chia thành phần, tổng trọng số của tập con của phần tử đầu tiên là và trọng số của món đồ thứ là . Tổng giá trị trong trường hợp này là .
- Nếu món đồ thứ không được chọn, nghĩa là tổng trọng số cũng chính là tổng trọng số của tập con của phần tử đầu tiên. Tổng giá trị trong trường hợp này là .
Đến đây, ta chọn giá trị lớn hơn làm giá trị cuối cùng cho . Nói cách khác, ta có công thức truy hồi:
Trường hợp cơ sở của bài toán trên là vì giá trị của một tập rỗng là , với vì ta không thể chọn một tập rỗng có giá trị khác . Như vậy, công thức đầy đủ cho là:
Đáp án cuối cùng cho bài toán là:
Như vậy, ta đã đưa ra lời giải cho bài toán quy hoạch động cái túi kinh điển và cơ bản nhất với độ phức tạp .
¶ Cài đặt
Sau đây là code tham khảo cho lời giải trên theo kiểu cài đặt Top-down:
using ll = long long;
bool ready[110][100010];
ll dp[110][100010], w[110], v[110];
ll solve (int i, int j) {
if (i == 0)
return (j == 0 ? 0 : LLONG_MIN);
if (ready[i][j]) return dp[i][j];
ready[i][j] = 1, dp[i][j] = solve(i - 1, j);
if (j >= w[i] && solve(i - 1, j - w[i]) != LLONG_MIN)
dp[i][j] = max(dp[i][j], solve(i - 1, j - w[i]) + v[i]);
return dp[i][j];
}
Để khử đệ quy và bỏ bảng ready, ta có thể chuyển sang kiểu cài đặt Bottom-up:
// khởi tạo bảng dp & trường hợp cơ sở
for (int i = 0; i <= n; i++)
fill(dp[i], dp[i] + C + 1, LLONG_MIN);
dp[0][0] = 0;
// tính giá trị cho mọi trạng thái
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= C; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= w[i] && dp[i - 1][j - w[i]] != LLONG_MIN)
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
// tính đáp án cuối cùng
cout << *max_element(dp[n], dp[n] + C + 1);
Do sự tiện lợi cũng như hiệu quả về cả mặt thời gian và bộ nhớ, cách cài đặt này thường được ưu tiên hơn so với Top-down.
¶ Tối ưu bộ nhớ
¶ Sử dụng mảng phần tử
Phân tích công thức quy hoạch động như trên, ta thấy rằng việc tính toán các giá trị chỉ phụ thuộc vào giá trị của . Do đó, ta chỉ cần duy trì giá trị của dòng liên tiếp của bảng . Từ đây, ta có thể giảm độ phức tạp bộ nhớ bằng cách chỉ sử dụng bảng có dòng rồi thay phiên nhau đóng vai trò là dòng được tính (dòng thứ ) và dòng được truy hồi (dòng thứ ).
Code tham khảo 1
for (int i = 0; i < 2; i++)
fill(dp[i], dp[i] + C + 1, LLONG_MIN);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int t = i & 1;
for (int j = 0; j <= C; j++) {
dp[t][j] = dp[t ^ 1][j];
if (j >= w[i] && dp[t ^ 1][j - w[i]] != LLONG_MIN)
dp[t][j] = max(dp[t][j], dp[t ^ 1][j - w[i]] + v[i]);
}
}
cout << *max_element(dp[n & 1], dp[n & 1] + C + 1);
¶ Sử dụng mảng phần tử
Ta thậm chí còn có thể bỏ hẳn một chiều của bảng dp bằng cách duyệt biến ngược từ về . Lúc này, ta có thể hiểu rằng tại mọi thời điểm, các ô trong khoảng của mảng lưu giá trị của dòng được tính còn các ô trong khoảng lưu giá trị của dòng được truy hồi.
Lưu ý rằng việc duyệt từ đến sẽ cho ra giá trị sai, ta có thể quan sát ví dụ sau: do trạng thái đã được xử lý trước nên việc lấy lại ô nhớ thứ để cập nhật ô nhớ lại trở thành lấy để tính .
Thay vào đó, ta cần lấy để tính .
Code tham khảo 2
fill(dp, dp + C + 1, LLONG_MIN);
dp[0] = 0; // trường hợp cơ sở
for (int i = 1; i <= n; i++)
for (int j = C; j >= w[i]; j--)
if (dp[j - w[i]] != LLONG_MIN)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << *max_element(dp, dp + C + 1);
Tuy có cùng độ phức tạp nhưng sau khi áp dụng các tối ưu bộ nhớ, tốc độ của thuật toán cũng được tối ưu một cách đáng kể. Cụ thể, với mấy chấm của VNOJ, độ hiệu quả (theo test có kết quả tệ nhất) của ba cách cài đặt được thể hiện qua bảng sau:
| Tiêu chí đánh giá | Top-down | Bottom-up | Bottom-up có tối ưu bộ nhớ (code tham khảo 2) |
|---|---|---|---|
| Thời gian chạy | giây | giây | giây |
| Bộ nhớ | MB | MB | MB |
¶ Đảo nhãn
Trong trường hợp giới hạn của trọng số lớn nhưng giá trị của các món đồ lại nhỏ (ví dụ như bài Knapsack 2), ta có thể dùng tham số giá trị để đặt trạng thái còn trọng số để tính. Khi đó, hàm Quy hoạch động sẽ là là trọng số nhỏ nhất nếu chọn ra tập các món đồ có tổng giá trị từ món đồ đầu tiên.
Với định nghĩa mới, ta có công thức truy hồi như sau:
Cuối cùng, ta tìm giá trị lớn nhất sao cho , tức là mức giá trị lớn nhất sao cho tồn tại một cách chọn có tổng trọng số không quá . Độ phức tạp của thuật toán lúc này là .
¶ Bài toán Subset sum
¶ Bài toán
¶ Đề bài
Cho món đồ và một số nguyên , mỗi món đồ được gán trọng số . Đếm số tập con các món đồ có tổng đúng bằng , modulo .
Nói cách khác, đếm số tập sao cho , rồi in đáp án modulo .
¶ Giới hạn
- .
- .
¶ Lời giải Quy hoạch động
Với ý tưởng đặt trạng thái tương tự với bài toán 0/1 Knapsack, ta gọi là số tập con các món đồ có tổng đúng bằng , nếu chỉ xét món đồ đầu tiên. Nói cách khác, là số tập sao cho . Để tìm công thức truy hồi, ta cũng xét hai trường hợp cho việc chọn hay không chọn món đồ thứ :
- Nếu món đồ thứ không được chọn, tức toàn bộ tổng là của món đồ đầu tiên. Số cách chọn theo trường hợp này là .
- Nếu món đồ thứ được chọn, tức nó đóng góp đơn vị vào tổng , phần còn lại sẽ là của món đồ đầu tiên. Số cách chọn theo trường hợp này là .
Kết hợp các trường hợp cơ sở, ta có công thức truy hồi:
Tương tự, nếu bài toán là kiểm tra sự tồn tại của một tập con có tổng là thay vì đếm số tập, ta có thể thay đổi công thức truy hồi như sau:
Với là ký hiệu của phép bitwise OR.
Tương tự lời giải cho bài toán 0/1 Knapsack như trên, độ phức tạp của thuật toán này là .
¶ Cài đặt
dp[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = C; j >= w[i]; j--)
dp[j] += dp[j - w[i]]; // thêm modulo khi cần
cout << dp[C];
¶ Tối ưu bài toán kiểm tra sự tồn tại
¶ Đề bài
Cho món đồ và một số nguyên , mỗi món đồ được gán trọng số . Kiểm tra sự tồn tại của một tập con các món đồ có tổng đúng bằng .
Nói cách khác, kiểm tra xem có tồn tại một tập sao cho hay không.
¶ Giới hạn (thay đổi)
¶ Tối ưu 1
Xét các truy hồi trên dòng thứ của bảng Quy hoạch động, ta thấy mọi ô ở dòng cột đều lấy giá trị từ dòng cột và theo công thức truy hồi :
Điều này cũng tương tự với việc dịch chuyển toàn bộ các phần tử của sang phải lần, rồi thực hiện bitwise OR với các phần tử ban đầu:
Nếu lưu mỗi dòng của bảng Quy hoạch động dưới dạng cấu trúc dữ liệu bitset, ta có thể biến đổi thao tác dịch chuyển các phần tử thành phép dịch bit sang trái. Khi đó, công thức truy hồi là:
Việc sử dụng cấu trúc dữ liệu bitset sẽ giúp giảm cả độ phức tạp thời gian lẫn bộ nhớ xuống hoặc lần.
Code tham khảo 3
bitset<2'000'001> exist;
exist.set(0); // gán exsit[0] = 1, trường hợp cơ sở
for (int u : w)
exist |= (exist << u);
cout << exist[C];
¶ Tối ưu 2
Xét hai danh sách món đồ ( phần tử) và danh sách ( phần tử), cả hai đều có thể tạo ra mọi số nguyên từ đến bằng cách lấy tổng một tập con bất kỳ. Tuy nhiên, danh sách thứ hai lại có số phần tử chưa đến một nửa danh sách đầu tiên.
Từ đó, ta có thể đưa ra ý tưởng rút gọn một số phần tử trong danh sách món đồ mà vẫn không ảnh hưởng kết quả của bài toán. Cụ thể, với một giá trị bất kỳ xuất hiện lần, ta thay phần tử này thành phần tử và phần tử .
Chứng minh
Với một danh sách có giá trị xuất hiện tối thiểu lần, ta tách chúng ra thành hai danh sách con và danh sách là phần còn lại. Gọi là tập các tổng tập con của dãy . Dễ thấy
Với phép hai tập hợp là ký hiệu của tổng Minkowski.
Mặt khác, ta có:
Do đó:
Sau các bước biến đổi, chúng ta còn lại một mảng có độ dài với .
Chứng minh
Dễ thấy, nếu có một giá trị xuất hiện ít nhất lần, nghĩa là các bước biến đổi vẫn chưa được thực hiện xong. Do đó, ta có thể chắc chắn rằng một giá trị chỉ xuất hiện ít nhất lần. Khi đó, tổng của một danh sách món đồ phải có giá trị tối thiểu là:
Nói cách khác:
Do đó, cận trên của độ dài mảng là .
Để thực hiện thao tác biến đổi danh sách món đồ thuận tiện hơn, ta sử dụng thuật toán sau: Ta duy trì mảng thống kê của dãy rồi duyệt mọi mức trọng lượng từ đến . Với mức trọng lượng nào đó, đặt:
Ta thực hiện xóa đi phần tử có trọng lượng rồi thêm phần tử có trọng lượng , sau đó, đưa các phần tử có trọng lượng còn lại vào danh sách món đồ mới.
Code tham khảo 4
// chuẩn bị mảng thống kê
for (int u : components) cnt[u]++;
exist.set(0);
for (int i = 1; i <= S; i++) {
if (!cnt[i]) continue;
int delta = (cnt[i] - 1) / 2;
cnt[i] -= (delta * 2);
if (i * 2 <= S) cnt[i * 2] += delta;
for (int j = 0; j < cnt[i]; j++) exist |= (exist << i);
}
Như vậy, ta đã có thuật toán Quy hoạch động tối ưu với độ phức tạp .
¶ Bỏ phần tử với bài toán đếm
Giả sử ta cần xử lý bài toán Subset Sum theo dạng "online" với ba loại truy vấn sau:
- Thêm một phần tử có trọng số vào cái túi.
- Bỏ một phần tử có trọng số khỏi cái túi.
- Cho biết số tập con có tổng đúng bằng .
Với thao tác thêm, ta thực hiện tương tự ý tưởng Quy hoạch động cái túi được trình bày như trên:
for (int j = C; j >= weight; j--)
dp[j] += dp[j - weight]; // thêm modulo khi cần
Đối với thao tác bỏ phần, để ý rằng thứ tự thêm các món đồ vào cái túi không ảnh hưởng đến kết quả bài toán, do đó, ta giả sử phần tử cần bỏ cũng là phần tử cuối cùng được thêm. Khi đó, ta chỉ cần thiết kế thao tác "undo" -- hủy bỏ thay đổi của vòng lặp trên:
for (int j = weight; j <= C; j++)
dp[j] -= dp[j - weight]; // thêm modulo khi cần
Lưu ý khi cài đặt
Đối với các bài toán đếm liên quan đến Subset Sum, ta thường được yêu cầu in ra đáp án modulo một số nguyên tố (như hoặc ). Do đó, quá trình tính toán Quy hoạch động sẽ gọi toán tử modulo rất nhiều. Điều này có thể làm chậm tốc độ của chương trình.
Ta thường phải khử phép modulo bằng cách:
- Viết hàm
add(a, b)vàsub(a, b)để tính và với (chỉ sử dụng phép cộng/trừ vàif/else).- Sử dụng
ModInt, bạn đọc có thể tham khảo template này.
¶ Bài tập ứng dụng
¶ Singapore NOI 2018 - Knapsack (0/1 Knapsack có bản sao)
¶ Đề bài
Cho loại món đồ và một giới hạn , loại thứ có trọng lượng , giá trị và số lượng . Tìm một tập con các món đồ sao cho tổng trọng số không quá và tổng giá trị đạt cực đại.
Nói cách khác, tìm một dãy sao cho với mọi , và đạt cực đại.
¶ Giới hạn
(Lưu ý, biến trong đề bài gốc đã được thay thế thành biến để đồng nhất với cách đặt tên biến trong bài viết này)
¶ Lời giải quy về quy hoạch động cái túi kinh điển
Nhận xét rằng với mỗi mức cân nặng , ta chỉ có thể chọn tối đa món đồ. Hơn nữa, khi đã cố định các một mức cân nặng, ta chỉ việc tham lam chọn món đồ có giá trị lớn nhất. Nói cách khác, với mỗi mức cân nặng , món đồ có giá trị lớn thứ trở đi sẽ không bao giờ được chọn vào tập tối ưu.
Dựa vào nhận xét trên, ta "lọc" lại các món đồ và chỉ xét các món đồ tiềm năng, tức món đồ có giá trị lớn nhất với mỗi mức cân nặng . Khi đó, số món đồ ta cần xét chỉ còn:
Khi đó, nếu thực hiện quy hoạch động trên tập món đồ tiềm năng, độ phức tạp thời gian sẽ là .
Code tham khảo 5
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
ll V[mn], W[mn], K[mn], dp[2020], used[2020];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int S, n; cin >> S >> n;
for (int i = 1; i <= n; i++) cin >> V[i] >> W[i] >> K[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(all(ord), [&] (int a, int b) { return V[a] > V[b]; });
int t = 0, counter = 0;
for (int i : ord) {
for (int iter = 0; iter < K[i]; iter++) {
if (used[W[i]] * W[i] > S) break;
for (int j = S; j >= W[i]; j--)
dp[j] = max(dp[j], dp[j - W[i]] + V[i]);
used[W[i]]++;
}
}
cout << dp[S];
return 0;
}
¶ Lời giải sử dụng deque trick
Tuy nhiên, trong trường hợp giới hạn của lớn (ví dụ, và ), cách làm như trên là chưa hợp lý. Thay vào đó, ta có thể xử lý bài toán trên với lời giải thứ hai đó là sử dụng kỹ thuật tìm max-min trong đoạn tịnh tiến hay deque trick.
Vẫn giữ nguyên cách đặt trạng thái là tổng giá trị lớn nhất có thể đạt được nếu chọn tập có tổng trọng lượng và chỉ xét loại đồ đầu tiên. Nếu chọn (với ) món đồ cho loại đồ thứ , tổng giá trị tối đa mà ta có là . Do đó, công thức truy hồi trong trường hợp này là:
Để đơn giản hóa bài toán, ta tạm bỏ qua giới hạn . Khi đó, với mỗi trạng thái trên bảng quy hoạch động, ta truy hồi về các trạng thái trên dòng , cột tức các cột có chỉ số đồng dư với theo modulo .
Như vậy, ta có thể biến đổi công thức lại thành:
Tách công thức độc lập theo , ta có:
Như vậy, ý tưởng chung của thuật toán là với mọi , ta chia các trạng thái quy hoạch động ở dòng thành theo modulo . Ở nhóm thứ , ta tạo dãy gồm các giá trị sao cho và:
Để tính , xét nhóm thứ , ta tính giá trị nhỏ nhất của đoạn con liên tiếp có độ dài kết thúc tại phần tử có chỉ số (theo cột của bảng quy hoạch động) là . Để hỗ trợ tính toán giá trị nhỏ nhất của các đoạn tịnh tiến, ta sử dụng deque trick giúp truy vấn trong .
Như vậy, ta đã có một lời giải khác cho bài toán nêu trên có độ phức tạp .
Code tham khảo 6
Lưu ý, đây chỉ là lời giải đạt điểm trên nền tảng oj.uz do giới hạn của bài tập không thích hợp với độ phức tạp thuật toán.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
ll V[mn], W[mn], K[mn], dp[2][2020], used[2020];
struct dqTrick {
deque<ll> dq;
void push (ll x) {
while (dq.size() && dq.back() < x) dq.pop_back();
dq.push_back(x);
}
void pop (ll x) {
if (dq.size() && dq.front() == x) dq.pop_front();
}
ll best() { return (dq.empty() ? LLONG_MIN : dq.front()); }
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int S, n; cin >> S >> n;
for (int i = 1; i <= n; i++) cin >> V[i] >> W[i] >> K[i];
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
sort(all(ord), [&] (int a, int b) { return V[a] > V[b]; });
int t = 0;
for (int i : ord) {
if (used[W[i]] * W[i] > S) continue;
vector<dqTrick> opt(W[i]);
for (int j = 0; j <= S; j++) {
int R = j % W[i], D = j / W[i];
opt[R].push(dp[t ^ 1][j] - D * V[i]);
if (j >= W[i] * (K[i] + 1))
opt[R].pop(dp[t ^ 1][j - W[i] * (K[i] + 1)] - (D - K[i] - 1) * V[i]);
dp[t][j] = opt[R].best() + D * V[i];
}
t ^= 1, used[W[i]] += K[i];
}
cout << dp[t ^ 1][S];
return 0;
}
¶ Codeforces 755F - PolandBall and Gifts
¶ Giới hạn
Cho một hoán vị độ dài và một số nguyên , đảm bảo với mọi . Biết rằng sẽ có phần tử bị xóa đi (không đánh số lại các phần tử chưa bị xóa). Ta gọi phần tử thứ là đặc biệt khi thỏa đồng thời:
- Phần tử thứ chưa bị xóa.
- Phần tử thứ thỏa chưa bị xóa.
Đếm số phần tử không đặc biệt ít nhất và nhiều nhất ( yêu cầu riêng biệt) khi xóa phần tử của hoán vị .
¶ Giới hạn
¶ Biến đổi thành đồ thị
Với mọi phần tử , ta dựng cạnh có hướng . Khi đó, ta có một đồ thị mà mỗi thành phần liên thông là một chu trình. Do sự độc lập giữa các thành phần liên thông, với cả hai yêu cầu, ta sẽ xử lý riêng từng thành phần liên thông rồi kết hợp các kết quả lại với nhau.
Lúc này, bài toán của chúng ta là cho một chu trình gồm đỉnh. Tìm cách xóa cạnh sao cho số đỉnh không có cạnh vào/ra là ít nhất và nhiều nhất.
¶ Bài toán cực đại hóa
Ta sẽ lần lượt giải quyết từng yêu cầu của bài toán, bắt đầu với yêu cầu cực đại hóa số đỉnh không có cạnh vào/ra. Dễ thấy, ta có thể tham lam xóa/giữ các cạnh xen kẽ nhau để có phương án tối ưu.
Ví dụ, với chu trình gồm đỉnh, thứ tự xóa cạnh sau là tối ưu:
Cụ thể hơn, xét một chu trình gồm đỉnh, khi xóa cạnh đầu tiên, ta xóa được đỉnh đặc biệt cho mỗi cạnh. Với cạnh tiếp theo, ta xóa được đỉnh đặc biệt cho mỗi cạnh. Các cạnh còn lại không đóng góp gì vào đáp án.
Gọi cạnh loại là cạnh mà khi xóa đi sẽ kéo theo đỉnh đặc biệt bị xóa. Ta thống kê được số cạnh loại và cho cả đồ thị và đặt là . Sau đó, tiếp tục sử dụng tham lam và xóa cạnh loại và cạnh loại .
Như vậy, yêu cầu này có thể được xử lý trong .
¶ Bài toán cực tiểu hóa
Đối với bài toán cực tiểu hóa, ta lại dùng ý tưởng tham lam nhưng lần này, ta sẽ xóa các cạnh liên tiếp. Với chiến lược đó, mỗi thành phần liên thông sẽ có đúng cạnh loại , cạnh loại và có cạnh loại .
Một nhận xét quan trọng đó là một khi đã bắt đầu xóa cạnh cho một thành phần liên thông nào đó, ta sẽ tiến hành xóa tại thành phần liên thông đó cho đến khi hết cạnh. Lý do là số đỉnh đặc biệt bị xóa đi không tăng lên khi ta tiếp tục xóa tại một thành phần liên thông nào đó.
Như vậy, ta xét hai trường hợp:
- Nếu xóa được hết các cạnh thuộc các thành phần liên thông mà ta chọn để xóa, đáp án sẽ là .
- Nếu có một thành phần liên thông đang bị xóa dang dở, đáp án sẽ là .
Để kiểm tra trường hợp, ta lại quy bài toán đồ thị thành bài toán cái túi: mỗi thành phần liên thông được xem như một món đồ có trọng số bằng số đỉnh của nó. Nhiệm vụ của chúng ta là kiểm tra xem tồn tại một tập các thành phần liên thông có tổng số đỉnh là hay không.
Với thuật toán kết hợp hai tối ưu đã được trình bày ở phần Subset Sum, ta có thể xử lý yêu cầu này trong .
¶ Cài đặt
Để dễ dàng tách biệt các code xử lý hai yêu cầu khác nhau, mình sẽ sử dụng namespace. Ở mỗi namespace, mình cài đặt một hàm solve nhận vào danh sách kích thước các thành phần liên thông và trả về đáp án.
Code tham khảo 7
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e6 + 6;
bool vis[mn];
int p[mn], n, k;
namespace solveMin {
bitset<mn> exist;
int cnt[mn];
int solve (const vector<int> &components) {
for (int u : components) cnt[u]++;
exist.set(0);
for (int i = 1; i <= n; i++) {
if (!cnt[i]) continue;
int merged = (cnt[i] - 1) >> 1;
cnt[i] -= (merged << 1);
if ((i << 1) <= n) cnt[i << 1] += merged;
for (int j = 0; j < cnt[i]; j++) exist |= (exist << i);
}
return k + (exist[k] == 0);
}
};
namespace solveMax {
int solve (const vector<int> &components) {
vector<int> cnt(3);
for (int u : components)
cnt[2] += u >> 1, cnt[1] += u & 1;
int pickTwo = min(cnt[2], k);
return (pickTwo << 1) + min(cnt[1], k - pickTwo);
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> p[i];
// thực hiện DFS khử đệ quy trên đồ thị hàm
vector<int> components;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
int counter = 0;
for (int node = i; !vis[node]; node = p[node]) counter++, vis[node] = 1;
components.push_back(counter);
}
cout << solveMin::solve(components) << " "
<< solveMax::solve(components) << "\n";
return 0;
}
¶ Phụ lục
¶ Luyện tập thêm
- VNOJ, Cái túi 2
- MarisaOJ, Knapsack
- 2016 USP Try-outs, The Knapsack Problem
- AtCoder Beginner Contest 221, Jumping Sequence
- VNOI Cup 2024, Round 2, Love Charm
- JOI 2019, Growing Vegetable is Fun 3
- USACO Platinum, Exercise