Cái Túi 2 (BTKCATU2)

Nguồn: VinhDinhCoder Độ khó: Trung bình Quay lui Đệ quy Truy vết Quy hoạch động

Đề bài

BTKCATU2 – CÁI TÚI 2

Trong siêu thị tại gian hàng Black Friday có $n$ đồ vật, đồ vật thứ $i$ có trọng lượng là $W[i]$ và giá trị $V[i]$. Bạn được một phiếu mua hàng đặc biệt khi vào mua hàng tại gian hàng Black Friday ở siêu thị này. Khi sử dụng phiếu mua hàng này bạn được phép chọn một số đồ vật bất kỳ trên gian hàng miễn sao trọng lượng tối đa là $M$. Hỏi bạn có thể lấy đi những mặt hàng nào để giá trị bạn nhận được là tối đa.

Bạn hãy lập trình giải quyết bài toán trên với dữ liệu cho là danh sách $n$ mặt hàng tại gian hàng mà bạn có thể chọn. Bạn cần liệt kê được danh sách các mặt hàng mà mình lấy được.

Dữ liệu nhập:

• Dòng đầu tiên là hai số nguyên dương $n$ và $M$ $(1 \le n \le 24;\ 1 \le M \le 10^{11})$.
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $w[i]$ và $v[i]$ là trọng lượng và giá trị của đồ vật thứ $i$ $(1 \le w[i], v[i] \le 10^9)$.

Kết quả:

• Dòng 1 in một số nguyên $x$ là số đồ vật bạn lấy được.
• Dòng 2 bạn in số thứ tự của các vật phẩm được lấy đi (số thứ tự của các đồ vật theo thứ tự trong đầu vào).

Nếu có nhiều đáp án tối ưu, bạn có thể in đáp án tối ưu bất kỳ.

Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 128 MB.

Ví dụ – input

5 20
7 1
5 8
1 1
7 8
9 7

Ví dụ – output

4
1 2 3 4

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Đây là phần 2 của bài cái túi nha. Phần 1 (bài "Cái túi 1 ver 2" trên blog – cùng đề nhưng chỉ cần in ra tổng giá trị lớn nhất) mình đã giải thích kỹ hàm đệ quy quay lui rồi, nên ở đây những chỗ code giống phần 1 mình sẽ không giải thích lại, chỉ tập trung vào phần mới: làm sao biết được mình đã lấy những đồ vật nào.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Với các hệ thống web chấm bài giới hạn thời gian chạy tối đa chỉ 1 giây thì các bạn rất dễ rơi vào lỗi TLE (Time Limit Exceeded – chạy quá thời gian cho phép). Như mình đã nói rất nhiều lần: muốn an toàn thì số phép toán trên toàn bài chỉ nên ở ngưỡng $(3 \text{ đến } 5) \cdot 10^7$; một số hệ thống server mạnh hơn có thể nâng lên $10^8$ nhưng cũng hên xui nhé. Thực ra ta không cần đếm chi tiết từng phép toán, cứ canh theo số lần vòng lặp (hay số lần gọi đệ quy) chạy là được. Ngưỡng này là cho C/C++; Python, Java, C# chạy chậm hơn nên ngưỡng phải thấp hơn. Đề cho 2 giây thì nhân ngưỡng lên 2, 3 giây thì nhân 3, 100 ms thì chia 10, cứ thế thôi.

Tóm tắt đề cho bạn nào chưa hiểu: có $n \le 24$ đồ vật, đồ vật $i$ nặng $w[i]$ và có giá trị $v[i]$; túi chứa được tối đa $M$ (tới $10^{11}$). Chọn các đồ vật sao cho tổng trọng lượng $\le M$ và tổng giá trị lớn nhất, rồi in ra số lượng đồ vật đã chọn và số thứ tự của chúng.

Ví dụ: $n = 5$, $M = 20$, các đồ vật (trọng lượng, giá trị) là $(7, 1), (5, 8), (1, 1), (7, 8), (9, 7)$. Cách chọn tối ưu là lấy đồ vật 1, 2, 3 và 4: khối lượng $7 + 5 + 1 + 7 = 20 \le 20$, giá trị $1 + 8 + 1 + 8 = 18$ là lớn nhất. Vậy in ra $4$ (số đồ lấy) và dòng sau là $1\ 2\ 3\ 4$.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Quay lui + vector lưu vết · O(2ⁿ) · ACCách 2 (đọc thêm)QHĐ bottom-up + truy vết · khi M ≤ 1000

Cách 1Quay lui, dùng vector lưu các đồ vật đã chọn – O(2ⁿ)

Bước 1: viết lại hàm đệ quy thành hàm không trả về

Ở phần 1 mình dùng hàm đệ quy có trả về để tính giá trị lớn nhất. Ở bài này, để tiện in ra các đồ vật đã lấy, mình viết lại thành hàm không trả về, chỉ cần thay đổi một chút:

• Kết quả lưu vào một biến toàn cục res, lúc đầu res = 0.
• Hàm Try(n, M, val) thêm tham số val là tổng giá trị các món đồ đã lấy: đang xét các đồ vật $1..n$, túi còn chứa thêm được $M$.
• Điều kiện dừng: n == 0 (không còn gì để lấy) hoặc M == 0 (túi không chứa thêm được) thì cập nhật res bằng cách so với val, rồi return để không gọi đệ quy nữa.
• Trong mọi trường hợp ta đều có thể không lấy món thứ $n$, nên gọi luôn Try(n - 1, M, val): túi vẫn còn $M$, giá trị không đổi.
• Nếu w[n] <= M thì có thể lấy món thứ $n$: gọi Try(n - 1, M - w[n], val + v[n]).

Lúc đầu chưa lấy món gì nên gọi Try(n, M, 0). Đến đây là AC được phần 1 rồi.

Bước 2: thêm một vector lưu danh sách đồ vật đang chọn

Để làm phần 2, ta dùng thêm một tham số nữa trong hàm Try() để lưu danh sách các đồ vật đã chọn – có thể dùng vector, stack hay queue, nhưng vector là nhanh nhất nên mình dùng vector. Thêm một biến toàn cục vector<int> idRes có tác dụng giống res, chỉ khác là nó lưu vị trí các đồ vật của cách chọn tốt nhất.

Tham trị hay tham chiếu?

• Tham trị Try(..., vector<int> id): mỗi lần gọi, chương trình ngầm tạo ra một vector id mới và copy lại toàn bộ vector bên ngoài. Tiện ở chỗ trong hàm thay đổi thì bên ngoài không sao cả (2 biến khác nhau), nhưng copy liên tục như vậy rất tốn thời gian ⇒ dễ TLE.
• Tham chiếu Try(..., vector<int> &id): id trong hàm chính là id bên ngoài, không tốn thời gian copy. Bù lại phải cẩn thận vì trong thay đổi thì ngoài cũng thay đổi, nhất là khi đang đệ quy.

Mẹo cho cách tham chiếu: đã thêm vào thì phải xoá ra. Có push_back() trước khi gọi đệ quy thì phải có pop_back() ngay sau khi gọi xong, để trả vector về đúng trạng thái cũ cho các nhánh sau.

Vậy hàm mới là Try(ll n, ll M, ll val, vector<int> &id):

• Ở điều kiện dừng: nếu val > res (tìm được cách tốt hơn) thì gán res = val và idRes = id (chỉ copy khi có cách tốt hơn), rồi return như thường.
• Ở nhánh có lấy món thứ $n$: id.push_back(n), gọi đệ quy, rồi id.pop_back().
• Vì ta đi từ đồ vật thứ $n$ ngược về đồ vật đầu tiên nên danh sách số thứ tự bị lưu ngược; lúc in thì in từ cuối vector về đầu là được thứ tự tăng dần.

Minh hoạ cây quay lui

Em nhập $M$ và các đồ vật (mỗi đồ vật là một cặp w v, tối đa 5 đồ vật) rồi bấm Tiếp. Mỗi nút trên cây là một lần gọi Try: số trong nút là val, dòng nhỏ bên dưới là sức chứa còn lại M. Nhánh trái = không lấy món $n$, nhánh phải (xanh) = lấy món $n$; dấu ✗ đỏ là nhánh bị chặn vì w[n] > M. Để ý vector id được push_back rồi pop_back như thế nào nhé.

M w v của từng đồ vật

Ví dụ nhanh:

Sau đây là source code của mình cho ý tưởng trên:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

ll w[30], v[30];
ll res = 0;
vector<int> idRes;

void Try(ll n, ll M, ll val, vector<int> &id) {
    if(n == 0 || M == 0) {
        if(val > res) {
            res = val;
            idRes = id;
        }
        return;
    }
    Try(n - 1, M, val, id);
    if(w[n] <= M) {
        id.push_back(n);
        Try(n - 1, M - w[n], val + v[n], id);
        id.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, M;
    cin >> n >> M;
    for(int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }
    vector<int> id;
    Try(n, M, 0, id);
    cout << (int)idRes.size() << endl;
    for(int i = (int)idRes.size() - 1; i >= 0; --i) {
        cout << idRes[i] << " ";
    }
    return 0;
}

import sys
sys.setrecursionlimit(10000)

n, M = map(int, input().split())
w = [0] * (n + 1)
v = [0] * (n + 1)
for i in range(1, n + 1):
    w[i], v[i] = map(int, input().split())

res = 0
idRes = []

def Try(n, M, val, id):
    global res, idRes
    if n == 0 or M == 0:
        if val > res:
            res = val
            idRes = id[:]          # sao chép danh sách hiện tại
        return
    Try(n - 1, M, val, id)
    if w[n] <= M:
        id.append(n)
        Try(n - 1, M - w[n], val + v[n], id)
        id.pop()

Try(n, M, 0, [])
print(len(idRes))
print(*idRes[::-1])

Giải thích một số chỗ trong code:

1. vector<int> id; trong main: lúc đầu tạo vector id rỗng vì chưa chọn phần tử nào, từ đó mới gọi Try(n, M, 0, id).
2. Vòng for cuối in idRes từ cuối về đầu, vì các đồ vật được thêm vào theo thứ tự $n, n - 1, \dots, 1$.
3. Bản Python dùng list (giống vector) với append/pop; khi cập nhật thì phải sao chép id[:], nếu gán idRes = id thì 2 biến trỏ chung một list, các lần pop sau sẽ làm hỏng kết quả.

Dành cho bạn nào muốn biết hàm Try() mà vector để tham trị thì như thế này nha – viết dễ hơn (chỉ việc thêm vào, không cần xoá ra vì mỗi lần gọi đệ quy vector đã được copy sang biến khác) nhưng chạy sẽ bị TLE đó:

void Try(ll n, ll M, ll val, vector<int> id) {
    if(n == 0 || M == 0) {
        if(val > res) {
            res = val;
            idRes = id;
        }
        return;
    }
    Try(n - 1, M, val, id);
    if(w[n] <= M) {
        id.push_back(n);
        Try(n - 1, M - w[n], val + v[n], id);
    }
}

C++▶ Chạy tay từng dòng codeCách 1: quay lui Try(n, M, val, id), push_back trước khi lấy món n, pop_back sau khi gọi xong.

Dữ liệu vào (stdin) – sửa thoải mái3 5 3 4 2 3 4 5

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6ll w[30], v[30];

7ll res = 0;

8vector<int> idRes;

9

10void Try(ll n, ll M, ll val, vector<int> &id) {

11 if(n == 0 || M == 0) {

12 if(val > res) {

13 res = val;

14 idRes = id;

15 }

16 return;

17 }

18 Try(n - 1, M, val, id);

19 if(w[n] <= M) {

20 id.push_back(n);

21 Try(n - 1, M - w[n], val + v[n], id);

22 id.pop_back();

23 }

24}

25

26int main() {

27 ios_base::sync_with_stdio(0);

28 cin.tie(0);

29 cout.tie(0);

30 ll n, M;

31 cin >> n >> M;

32 for(int i = 1; i <= n; ++i) {

33 cin >> w[i] >> v[i];

34 }

35 vector<int> id;

36 Try(n, M, 0, id);

37 cout << (int)idRes.size() << endl;

38 for(int i = (int)idRes.size() - 1; i >= 0; --i) {

39 cout << idRes[i] << " ";

40 }

41 return 0;

42}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: độ sâu đệ quy tối đa $n$, vector id và idRes tối đa $n$ phần tử ⇒ $O(n)$.
• Thời gian: mỗi đồ vật có 2 lựa chọn lấy / không lấy nên tệ nhất có $2^n$ lá, tổng số lần gọi khoảng $2^{n+1}$. Với $n = 24$ là khoảng $3.3 \cdot 10^7$ lần gọi, vừa đúng ngưỡng an toàn. Mình đo bản C++ với test nặng nhất ($n = 24$, túi chứa được hết) chạy khoảng 0.1 giây.

Không gian$O(n)$

Thời gian$O(2^n)$

Lưu ý với Python

Cùng thuật toán, bản Python với $n = 24$ và túi chứa được hết đồ vật chạy mất khoảng 5 giây trên máy mình ⇒ sẽ TLE với giới hạn 1 giây. Bạn nào dùng Python thì chỉ nên xem để hiểu ý tưởng, nộp bài thì dùng C++ nhé.

Cách 2Đọc thêm: QHĐ bottom-up + truy vết (khi n, M ≤ 1000)

Giờ mình giả sử đề đổi thành $1 \le n, M, w[i] \le 1000$. Với $n = 1000$ thì cách quay lui ở trên chắc chắn TLE ($2^{1000}$!), còn chậm hơn cả phần 1 vì tốn thêm thời gian cho vector lưu vị trí. Lúc này phải dùng quy hoạch động.

Cả QHĐ top-down hay bottom-up đều tạo ra mảng 2 chiều f[n][M] và độ phức tạp trên lý thuyết bằng nhau. Top-down tốn thêm chút bộ nhớ và thời gian cho đệ quy, nhưng nhiều trường hợp không phải lấp đầy toàn bộ mảng (không tin thì anh em lấy code top-down của phần 1, in mảng f với test mẫu ra xem). Có điều chính vì không lấp đầy nên truy vết bằng top-down khá rắc rối, vì vậy ở đây ta dùng bottom-up: lấp đầy cả bảng rồi nhìn vào bảng tìm ra quy luật truy vết. Mình khuyên các bạn nên in bảng f ra sau khi chạy xong, nhìn vào đó là thấy quy luật ngay.

Công thức QHĐ (giống phần 1)

f[i][j] = giá trị lớn nhất lấy được khi xét $i$ đồ vật đầu tiên và túi chứa được tối đa $j$.
Nếu $w[i] \gt j$: f[i][j] = f[i-1][j]; ngược lại: f[i][j] = max(v[i] + f[i-1][j-w[i]], f[i-1][j]).

Truy vết: bắt đầu từ f[n][M], tức i = n, j = M:

• Nếu f[i][j] == f[i-1][j]: với $i - 1$ đồ vật đầu ta cũng đã đạt được giá trị lớn nhất đó, nên không cần lấy đồ vật $i$ (có thể vẫn có cách khác có lấy $i$ cũng tối ưu, nhưng không lấy cũng được). Xét tiếp f[i-1][j]: túi vẫn chứa được $j$.
• Ngược lại f[i][j] != f[i-1][j], mà theo công thức thì f[i][j] ≥ f[i-1][j], nên ở đây chính là lớn hơn. Ví dụ với $i - 1$ món đầu chỉ lấy được tối đa 8, còn với $i$ món lại lấy được tới 10 – thì chắc chắn ta phải lấy món thứ $i$. Thêm $i$ vào danh sách rồi xét tiếp f[i-1][j - w[i]]: túi chỉ còn chứa thêm được $j - w[i]$.
• Lặp đến khi $i = 0$ (hết đồ vật) hoặc $j = 0$ (túi hết chỗ).

Source code cho ý tưởng trên cho anh em tham khảo nha:

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

ll w[1005], v[1005];
ll f[1005][1005];

void solve(ll n, ll M) {
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= M; ++j) {
            if(w[i] > j) {
                f[i][j] = f[i - 1][j];
            }
            else {
                f[i][j] = max(v[i] + f[i - 1][j - w[i]], f[i - 1][j]);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, M;
    cin >> n >> M;
    for(int i = 1; i <= n; ++i) {
        cin >> w[i] >> v[i];
    }
    solve(n, M);
    int i = n, j = M;
    vector<int> idRes;
    while(i && j) {
        if(f[i][j] == f[i - 1][j]) {
            i--;
        }
        else {
            idRes.push_back(i);
            j -= w[i];
            i--;
        }
    }
    cout << (int)idRes.size() << endl;
    for(int i = (int)idRes.size() - 1; i >= 0; --i) {
        cout << idRes[i] << " ";
    }
    return 0;
}

n, M = map(int, input().split())
w = [0] * (n + 1)
v = [0] * (n + 1)
for i in range(1, n + 1):
    w[i], v[i] = map(int, input().split())

# f[i][j] = giá trị lớn nhất khi xét i đồ vật đầu, túi chứa tối đa j
f = [[0] * (M + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, M + 1):
        if w[i] > j:
            f[i][j] = f[i - 1][j]
        else:
            f[i][j] = max(v[i] + f[i - 1][j - w[i]], f[i - 1][j])

i, j = n, M
idRes = []
while i and j:
    if f[i][j] == f[i - 1][j]:
        i -= 1
    else:
        idRes.append(i)
        j -= w[i]
        i -= 1
print(len(idRes))
print(*idRes[::-1])

Giải thích một số chỗ trong cách làm trên:

1. while(i && j) chính là while(i != 0 && j != 0); viết không thì trình biên dịch tự hiểu ngầm là != 0.
2. Vì ta vẫn đi ngược từ dưới lên nên lúc in ra vẫn phải in ngược.

Thứ tự 2 lệnh khi lấy đồ vật i

Phải trừ j -= w[i] trước rồi mới i--. Code mình đăng hồi đó lỡ viết i--; trước rồi j -= w[i];, lúc này w[i] đã là trọng lượng của đồ vật $i - 1$ nên truy vết bị lệch – mình thử 500 bộ test ngẫu nhiên thì có tới 257 bộ in sai. Trong bài mình đã sửa lại thứ tự cho đúng nhé.

C++▶ Chạy tay từng dòng codeCách 2: lấp bảng f[i][j] bottom-up rồi truy vết từ f[n][M] ngược về.

Dữ liệu vào (stdin) – sửa thoải mái3 5 3 4 2 3 4 5

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3using namespace std;

4typedef long long ll;

5

6ll w[1005], v[1005];

7ll f[1005][1005];

8

9void solve(ll n, ll M) {

10 for(int i = 1; i <= n; ++i) {

11 for(int j = 1; j <= M; ++j) {

12 if(w[i] > j) {

13 f[i][j] = f[i - 1][j];

14 }

15 else {

16 f[i][j] = max(v[i] + f[i - 1][j - w[i]], f[i - 1][j]);

17 }

18 }

19 }

20}

21

22int main() {

23 ios_base::sync_with_stdio(0);

24 cin.tie(0);

25 cout.tie(0);

26 ll n, M;

27 cin >> n >> M;

28 for(int i = 1; i <= n; ++i) {

29 cin >> w[i] >> v[i];

30 }

31 solve(n, M);

32 int i = n, j = M;

33 vector<int> idRes;

34 while(i && j) {

35 if(f[i][j] == f[i - 1][j]) {

36 i--;

37 }

38 else {

39 idRes.push_back(i);

40 j -= w[i];

41 i--;

42 }

43 }

44 cout << (int)idRes.size() << endl;

45 for(int i = (int)idRes.size() - 1; i >= 0; --i) {

46 cout << idRes[i] << " ";

47 }

48 return 0;

49}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: bảng f có $(n + 1)(M + 1)$ ô ⇒ $O(n \cdot M)$.
• Thời gian: lấp bảng $O(n \cdot M)$, truy vết chỉ $O(n)$ vì mỗi bước $i$ giảm 1 ⇒ $O(n \cdot M)$. Với $n = M = 1000$ chỉ khoảng $10^6$ phép tính.

Không gian$O(n \cdot M)$

Thời gian$O(n \cdot M)$

Nhưng với bài Cái túi 2 thì không nha

Bài này $M$ lên tới $10^{11}$ nên không thể tạo bảng f[n][M] được, anh em chỉ quay lui như cách 1 thôi nha. Cách 2 là để các bạn biết thêm kỹ thuật truy vết QHĐ, rất hay dùng trong các bài cái túi có $M$ nhỏ.

Ghi chú của mình: vì đề cho in đáp án tối ưu bất kỳ, mình kiểm tra bằng một chương trình chấm riêng: các đồ vật in ra không trùng nhau, tổng trọng lượng $\le M$ và tổng giá trị bằng đúng giá trị tối ưu tìm bằng vét cạn mọi tập con. Code C++ và Python của cả 2 cách qua hết 500 bộ test ngẫu nhiên nhỏ ($n \le 10$). Với $n = 24$ bản C++ cách 1 chạy khoảng 0.1 giây; cách 2 với $n = M = 1000$ chạy khoảng 0.01 giây (C++) và 0.5 giây (Python).

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇