Bài toán chiếc balo 2 (BALO2)

Nguồn: Lớp dự tuyển ĐT2 – Chuyên ĐH Vinh Độ khó: Trung bình Quy hoạch động Bài toán cái túi Tối ưu bộ nhớ

Đề bài

DP – Bài toán chiếc balo2

Trong siêu thị có $n$ $(0 \lt n \le 1000)$ đồ vật, đồ vật thứ $i$ có trọng lượng là $w[i]$, $0 \lt w[i] \le 1000$ và giá trị là $v[i]$, $0 \lt v[i] \le 10^9$. Các mặt hàng ở đây có thể coi số lượng là vô hạn.

Một tên trộm đột nhập vào siêu thị, tên trộm mang một cái túi có thể chứa tối đa là $M$, lần này với các đồ vật có số lượng thoải mái nên tên trộm không áp dụng được kỹ thuật chọn như trước nữa để lấy được nhiều giá trị nhất mà tổng khối lượng không vượt quá chiếc túi. Chắc hẳn, sẽ tồn tại một cách lựa chọn thông minh khác.

Yêu cầu: Hãy chọn các vật sao cho đặt vừa trong chiếc túi mà tổng giá trị lớn nhất có thể. Mỗi vật có thể được chọn nhiều lần.

Input Specification:

• Dòng đầu tiên chứa hai số nguyên dương $n$ và $M$ $(0 \lt n \le 10^3,\ 0 \lt M \le 10^4)$.
• $n$ dòng tiếp theo mỗi dòng ghi 2 số nguyên $v_i$ và $w_i$ là giá trị và trọng lượng của đồ vật thứ $i$.

Output Specification:

• Ghi ra giá trị lớn nhất của các đồ vật mà tên trộm có thể lấy.

Giới hạn: Time limit: 1.0s · Memory limit: 4M.

Sample Input

3 45
40 12
60 20
50 15

Sample Output

150

(Ảnh chụp đề bị cắt mất phần Sample Output, đáp án $150$ ở trên là mình tự tính và kiểm tra lại bằng chương trình vét cạn.)

Lời mở đầu

Bữa giờ LeetCode hoài sợ anh em ngán 😅. Nay mình đi comment dạo thấy một bạn hỏi bài này: "Bác nào chỉ em thuật toán bài này với ạ. (Chú ý: bộ nhớ chỉ có 4m)". Bài này là phiên bản "không giới hạn số lượng" của bài toán cái túi kinh điển, và cái bẫy chính nằm ở chỗ bộ nhớ chỉ có 4MB. Mình đăng để anh em thử sức nhé, hy vọng mang đến được giá trị cho các bạn 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Giải thích ví dụ cho bạn nào chưa hiểu đề: túi chứa tối đa $M = 45$, có 3 loại đồ vật (giá trị, trọng lượng) là $(40, 12)$, $(60, 20)$, $(50, 15)$, mỗi loại lấy bao nhiêu cái cũng được. Lấy 3 cái loại 3: tổng trọng lượng $3 \cdot 15 = 45 \le 45$, tổng giá trị $3 \cdot 50 = 150$. Thử các cách khác như $12 + 12 + 20 = 44$ (giá trị $140$) hay $20 + 20 = 40$ (giá trị $120$) đều không bằng. Đáp án là 150.

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

Cách 1QHĐ bảng 2 chiều · đúng nhưng ~80MBCách 2QHĐ mảng 1 chiều · ~80KB

Cách 1Quy hoạch động bảng 2 chiều – O(n · M) bộ nhớ

Gọi dp[i][j] là tổng giá trị lớn nhất có thể đạt được khi chỉ dùng các loại đồ vật từ 1 đến $i$ và tổng trọng lượng không vượt quá $j$. Khi xét đến loại đồ vật thứ $i$, có 2 khả năng:

• Không lấy thêm cái nào của loại $i$: giá trị là dp[i - 1][j].
• Lấy thêm 1 cái loại $i$ (khi $j \ge w_i$): bỏ cái này ra thì phần còn lại là túi sức chứa $j - w_i$, và phần đó vẫn được dùng loại $i$ tiếp (vì số lượng vô hạn) ⇒ giá trị là dp[i][j - w[i]] + v[i].

Công thức truy hồi

$dp[i][j] = \max\big(dp[i-1][j],\ dp[i][j - w_i] + v_i\big)$ (vế thứ hai chỉ khi $j \ge w_i$), với $dp[0][j] = 0$. Đáp án là $dp[n][M]$.

Khác gì với balo thường (mỗi vật lấy 1 lần)?

Ở bài balo 0/1, vế thứ hai là dp[i - 1][j - w[i]] + v[i] (đã lấy vật $i$ thì phần còn lại chỉ được dùng vật $1..i-1$). Ở bài này đổi thành dp[i][j - w[i]], vì phần còn lại vẫn được lấy tiếp vật $i$. Chỉ khác đúng một chỉ số thôi các bạn 😉.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int n, M;
long long v[1005];
int w[1005];
long long dp[1005][10005];

int main(){
    cin >> n >> M;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= M; j++){
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
        }
    cout << dp[n][M];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, M = int(data[0]), int(data[1])
v = [0] * (n + 1)
w = [0] * (n + 1)
for i in range(1, n + 1):
    v[i] = int(data[2 * i])
    w[i] = int(data[2 * i + 1])

dp = [[0] * (M + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(M + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][M])

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

• Không gian: bảng dp có $(n + 1)(M + 1) \approx 1001 \cdot 10001 \approx 10^7$ ô long long (8 byte) ⇒ khoảng 80MB.
• Thời gian: $O(n \cdot M) = 10^7$ phép tính, rất nhanh.

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

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

Đúng nhưng tràn bộ nhớ (MLE)

Thời gian thì không vấn đề gì, nhưng 80MB gấp 20 lần giới hạn 4MB của đề ⇒ chắc chắn bị MLE (Memory Limit Exceeded) với test lớn. Và cũng không thể đổi sang int để tiết kiệm, vì đáp án có thể lên tới $10^9 \cdot 10^4 = 10^{13}$ (ví dụ 10000 cái vật nặng 1, giá trị $10^9$). Đây chính là chỗ mà bạn hỏi bài vướng.

Cách 2Quy hoạch động mảng 1 chiều – O(M) bộ nhớ

Nhìn lại công thức: hàng $i$ chỉ dùng tới hàng $i - 1$ (ngay trên) và chính hàng $i$. Vậy mình không cần giữ cả bảng, chỉ cần một mảng 1 chiều dp[0..M] rồi "ghi đè" lên nó khi xét từng loại đồ vật:

Công thức với mảng 1 chiều

Với mỗi đồ vật $(v, w)$, duyệt $j$ tăng dần từ $w$ đến $M$: $dp[j] = \max(dp[j],\ dp[j - w] + v)$.

Vì sao đúng? Tại thời điểm cập nhật dp[j]:

• dp[j] (vế trái của max) chưa bị ghi đè ở lượt này ⇒ nó chính là dp[i - 1][j].
• dp[j - w] có chỉ số nhỏ hơn nên đã được cập nhật ở lượt này rồi ⇒ nó chính là dp[i][j - w]. Đây đúng là cái mình cần: đã lấy vật $i$ rồi vẫn được lấy tiếp.

Chiều duyệt j quyết định tất cả

Nếu duyệt $j$ giảm dần (từ $M$ về $w$) thì dp[j - w] chưa được cập nhật ⇒ thành dp[i - 1][j - w], mỗi vật chỉ lấy được 1 lần ⇒ đó là balo 0/1. Bài này cho lấy vô hạn nên phải duyệt tăng dần nhé.

Một điểm hay nữa là mỗi đồ vật đọc vào xong là xử lý luôn, không cần lưu mảng $v$, $w$. Tổng bộ nhớ chỉ còn mảng dp $10001$ phần tử long long ≈ 80KB, thoải mái trong 4MB.

Minh hoạ cập nhật mảng dp

Các bạn nhập $M$ và danh sách đồ vật (mỗi đồ vật là một cặp "giá trị trọng lượng") rồi bấm Tiếp để xem mảng dp được cập nhật thế nào (cam: ô $j$ đang xét, xanh dương: ô $j - w$ được dùng, viền xanh lá: ô vừa tăng giá trị):

M Đồ vật (v w, …)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

long long dp[10005];

int main(){
    int n, M;
    cin >> n >> M;
    for(int i = 1; i <= n; i++){
        long long v;
        int w;
        cin >> v >> w;
        for(int j = w; j <= M; j++)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[M];
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, M = int(data[0]), int(data[1])
dp = [0] * (M + 1)
for i in range(1, n + 1):
    v = int(data[2 * i])
    w = int(data[2 * i + 1])
    for j in range(w, M + 1):
        if dp[j - w] + v > dp[j]:
            dp[j] = dp[j - w] + v
print(dp[M])

C++▶ Chạy tay từng dòng codeCách 2: đọc từng đồ vật, duyệt j tăng dần, dp[j] = max(dp[j], dp[j − w] + v).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4long long dp[10005];

5

6int main(){

7 int n, M;

8 cin >> n >> M;

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

10 long long v;

11 int w;

12 cin >> v >> w;

13 for(int j = w; j <= M; j++)

14 dp[j] = max(dp[j], dp[j - w] + v);

15 }

16 cout << dp[M];

17 return 0;

18}

ChậmVừaNhanhRất nhanh

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

• Không gian: $O(M)$, chỉ khoảng $80$KB cho mảng dp.
• Thời gian: vẫn $O(n \cdot M) \approx 10^7$ phép tính.

Không gian$O(M)$

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

Về bản Python

Bộ nhớ 4MB là rất chặt: riêng trình thông dịch Python khi khởi động đã tốn vài MB, và $10^7$ phép tính bằng Python thuần mất cỡ 2–3 giây, nên trên hệ thống chấm của bài này (1 giây, 4MB) gần như chỉ C++ là qua được. Bản Python ở trên để các bạn tham khảo ý tưởng thôi nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách cho ra $150$ với test của đề, và đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có cả giá trị tới $10^9$, vật nặng hơn túi), so với một chương trình vét cạn thử mọi số lượng của từng vật – khớp hết. Với test lớn nhất ($n = 1000$, $M = 10^4$): cách 2 C++ chạy khoảng 0.03 giây, Python khoảng 2–3 giây; cách 1 C++ chạy 0.09 giây nhưng dùng khoảng 81MB bộ nhớ, đúng như phân tích là sẽ bị MLE với giới hạn 4MB.

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 😇