Knapsack

IBa lô 0/1

Khi mỗi vật chỉ được lấy tối đa một lần, ta có bài ba lô 0/1: chọn một tập vật có tổng khối lượng không quá $W$, tổng giá trị lớn nhất. Mỗi vật có hai khả năng, lấy hoặc không lấy, và có lấy được hay không còn tùy sức chứa còn lại. Vậy trạng thái cần hai tham số: $dp_{i,c}$ là tổng giá trị lớn nhất khi chỉ xét $i$ vật đầu và tổng khối lượng không quá $c$.

Xét vật $i$. Không lấy nó thì còn lại $dp_{i-1,c}$. Lấy nó (nếu $w_i \le c$) thì được thêm $v_i$ và phần còn lại là $i - 1$ vật đầu với sức chứa $c - w_i$:

Đáp án là $dp_{n,W}$. Bảng có $(n + 1)(W + 1)$ ô, mỗi ô tính trong $O(1)$, tổng cộng $O(nW)$.

Hình dùng bốn vật $(w, v) = (3, 4), (2, 3), (4, 6), (1, 1)$ và $W = 6$. Ô cuối $dp_{4,6} = dp_{3,6}$ vì lấy thêm vật 4 chỉ được $dp_{3,5} + 1 = 8$, kém $9$. Ô $dp_{3,6} = dp_{2,2} + 6 = 9$ (lấy vật 3) và $dp_{2,2} = dp_{1,0} + 3$ (lấy vật 2), nên tập tốt nhất là vật 2 và vật 3, nặng $6$ và có giá trị $9$.

Điều kiện “không quá $c$” ứng với khởi tạo $dp_{0,c} = 0$ cho mọi $c$. Nếu đề đòi khối lượng đúng bằng $c$, chỉ $dp_{0,0} = 0$ còn các ô khác khởi tạo $-\infty$ (hoặc $+\infty$ khi tìm giá trị nhỏ nhất).

Hàng $i$ chỉ dùng hàng $i - 1$, nên ta giữ một mảng dp[c] và sửa tại chỗ: dp[c] = max(dp[c], dp[c - w] + v). Công thức cần dp[c - w] của hàng cũ, tức là khi chưa xét vật $i$. Vì $c - w < c$, nếu duyệt $c$ giảm dần thì ô $c - w$ chưa bị sửa trong lượt này. Nếu duyệt tăng dần, dp[c - w] đã chứa vật $i$ và vật sẽ bị lấy lại nhiều lần, tức là ta đã giải một bài khác (ba lô không giới hạn, ở mục sau). Với một vật $w = 2$, $v = 3$ và $W = 4$: duyệt giảm cho $dp = (0, 0, 3, 3, 3)$, duyệt tăng cho $(0, 0, 3, 3, 6)$ vì vật được lấy hai lần.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll w, v, W, dp[105];

signed main() {
    cin >> w >> v >> W;
    for (ll c = w; c <= W; c++) dp[c] = max(dp[c], dp[c - w] + v);
    cout << dp[W] << '\n';
}

ChạyInput3 5 7

Output10

Ví dụTủ Sách Trong Ngân Sách

Đề. Cửa hàng có $n \le 1000$ quyển sách khác nhau; quyển $i$ giá $h_i$ và có $s_i$ trang ($h_i, s_i \le 1000$). Mỗi quyển mua tối đa một lần. Chọn các quyển sao cho tổng giá không quá $x \le 10^5$ và tổng số trang lớn nhất.

Lời giải. Đây đúng là ba lô 0/1 với khối lượng là giá sách và giá trị là số trang. Dùng một mảng, duyệt ngân sách từ $x$ xuống $h_i$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, x, h[1005], s[1005], dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (ll i = 1; i <= n; i++) cin >> h[i];
    for (ll i = 1; i <= n; i++) cin >> s[i];
    for (ll i = 1; i <= n; i++)
        for (ll c = x; c >= h[i]; c--) dp[c] = max(dp[c], dp[c - h[i]] + s[i]);
    cout << dp[x] << '\n';
}

ChạyInput5 13
6 4 7 3 9
8 5 10 4 13

Output18

Độ phức tạp: $O(nx)$, với $n = 1000$ và $x = 10^5$ cần khoảng $10^8$ phép tính.

IIBa lô không giới hạn: đổi tiền

Khi mỗi vật được lấy bao nhiêu lần cũng được, ta có ba lô không giới hạn. Đổi tiền là ví dụ quen thuộc nhất: có các mệnh giá $c_1, \dots, c_k$, mỗi mệnh giá dùng bao nhiêu đồng cũng được. Tạo tổng đúng bằng $x$ bằng ít đồng nhất.

Cách nghĩ đầu tiên là tham lam (bài 0.5): luôn lấy đồng lớn nhất không vượt phần còn lại. Với các mệnh giá $\{1, 3, 4\}$ và $x = 6$, tham lam lấy $4 + 1 + 1$ ($3$ đồng), trong khi $3 + 3$ chỉ cần $2$ đồng. Lấy đồng lớn trước có thể phá hỏng phần còn lại, nên ta xét mọi khả năng một cách có hệ thống.

Gọi $dp_s$ là số đồng ít nhất để tạo tổng đúng $s$, bằng $+\infty$ nếu không tạo được. Trong một phương án tối ưu cho $s$, lấy ra một đồng bất kỳ, mệnh giá $c$; phần còn lại tạo tổng $s - c$ và phải dùng ít đồng nhất có thể. Ta chưa biết $c$ là mệnh giá nào nên thử tất cả:

Số hạng bằng $+\infty$ thì bỏ qua. Duyệt $s$ tăng dần vì $dp_s$ phụ thuộc các ô nhỏ hơn. Với $\{1, 3, 4\}$ ta có $dp_{0..6} = (0, 1, 2, 1, 1, 2, 2)$; riêng $dp_6 = 1 + \min(dp_5, dp_3, dp_2) = 2$.

Ví dụÍt Đồng Xu Nhất

Đề. Có $n \le 100$ mệnh giá đồng xu đôi một khác nhau, mỗi mệnh giá dùng tùy ý. Tạo tổng đúng bằng $x \le 10^6$ với ít đồng nhất; in $-1$ nếu không tạo được.

Lời giải. Dùng công thức trên với $dp_s$ khởi tạo $10^{18}$ cho $s > 0$; tổng không tạo được vẫn giữ giá trị rất lớn, nên cộng thêm $1$ không làm nó nhỏ đi hay tràn số. Cuối cùng, nếu $dp_x$ còn là giá trị rất lớn thì in $-1$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
ll n, x, c[105], dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll s = 1; s <= x; s++) {
        dp[s] = 1e18;
        for (ll i = 1; i <= n; i++)
            if (c[i] <= s) dp[s] = min(dp[s], dp[s - c[i]] + 1);
    }
    if (dp[x] >= 1e18) cout << -1 << '\n';
    else cout << dp[x] << '\n';
}

ChạyInput3 10
4 6 7

Output2

Độ phức tạp: $O(nx)$, với $n = 100$ và $x = 10^6$ cần khoảng $10^8$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, x, c[10], dp[100];

signed main() {
    cin >> n >> x;
    for (ll i = 1; i <= n; i++) cin >> c[i];
    for (ll s = 1; s <= x; s++)
        for (ll i = 1; i <= n; i++)
            if (c[i] <= s) dp[s] = min(dp[s], dp[s - c[i]] + 1);
    cout << dp[x] << '\n';
}

ChạyInput1 3
2

Output0

Đổi câu hỏi thành đếm số cách thì trước hết phải nói rõ hai cách khác nhau khi nào. Hai cách hiểu cho hai bài toán, và hai đoạn code chỉ khác nhau ở thứ tự của hai vòng for.

Nếu $1 + 2$ và $2 + 1$ là hai cách (dãy có thứ tự), mỗi dãy có đúng một phần tử cuối $c$, bỏ nó đi còn một dãy tạo tổng $s - c$. Vậy $dp_s = \sum_{c_i \le s} dp_{s - c_i}$ (tổng các $dp_{s-c_i}$ qua mọi mệnh giá $c_i \le s$), với $dp_0 = 1$ (dãy rỗng). Tổng $s$ nằm ở vòng ngoài, mệnh giá ở vòng trong.

Nếu chỉ quan tâm mỗi mệnh giá dùng bao nhiêu đồng (tập mệnh giá), ta xử lý lần lượt từng mệnh giá để mỗi tập chỉ được sinh một lần. Gọi $dp_{k,s}$ là số cách tạo $s$ chỉ dùng $k$ mệnh giá đầu. Hoặc không dùng mệnh giá $c_k$, còn $dp_{k-1,s}$ cách; hoặc dùng ít nhất một đồng $c_k$, bỏ một đồng ấy đi thì còn $dp_{k,s-c_k}$ cách:

Nén thành một mảng, mệnh giá ở vòng ngoài và $s$ tăng dần ở vòng trong: dp[s] += dp[s - c]. Duyệt tăng chính là để dp[s - c] đã chứa các cách dùng $c$. Chương trình dưới in số dãy có thứ tự (f) rồi số tập mệnh giá (g).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7, N = 1e6 + 5;
ll n, x, c[105], f[N], g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (ll i = 0; i < n; i++) cin >> c[i];
    f[0] = g[0] = 1;
    for (ll s = 1; s <= x; s++)
        for (ll i = 0; i < n; i++)
            if (c[i] <= s) f[s] = (f[s] + f[s - c[i]]) % MOD;
    for (ll i = 0; i < n; i++)
        for (ll s = c[i]; s <= x; s++) g[s] = (g[s] + g[s - c[i]]) % MOD;
    cout << f[x] << '\n' << g[x] << '\n';
}

ChạyInput2 5
1 2

Output8
3

Độ phức tạp: $O(nx)$ cho mỗi cách đếm, với $n = 100$ và $x = 10^6$ cần khoảng $2 \cdot 10^8$ phép tính.

Với $x = 5$ và hai mệnh giá $1, 2$: có $3$ tập ($2+2+1$, $2+1+1+1$, năm đồng $1$) nhưng $8$ dãy có thứ tự, vì ba tập đó cho lần lượt $3$, $4$ và $1$ cách xếp. Đổi chỗ hai vòng for là đổi sang bài toán khác, nên phải đọc kỹ đề xem “cách” có phân biệt thứ tự không.

IIITổng con: những tổng nào tạo được

Có $n$ thẻ, thẻ $i$ mang số nguyên dương $x_i$, mỗi thẻ chọn tối đa một lần. Tổng nào của một tập thẻ có thể đạt được? Đây là ba lô 0/1 nhưng không cần giá trị: chỉ hỏi đúng hay sai. Gọi $ok_s$ là “có tập thẻ có tổng đúng $s$ hay không”, $ok_0$ đúng. Khi thêm thẻ $x$, tổng $s$ tạo được nếu trước đó đã tạo được $s$, hoặc đã tạo được $s - x$:

Giống ba lô 0/1, ta duyệt $s$ từ lớn xuống nhỏ để mỗi thẻ chỉ được dùng một lần.

Ví dụDanh Sách Tổng Khả Dụng

Đề. Có $n \le 100$ thẻ, thẻ $i$ mang số nguyên dương $x_i \le 1000$. In tất cả các tổng dương khác nhau của các tập con không rỗng, theo thứ tự tăng dần: dòng đầu là số lượng tổng, dòng sau là các tổng.

Lời giải. Tổng lớn nhất là tổng mọi thẻ, không quá $10^5$. Khi thêm thẻ $x$, ta cộng $x$ vào tổng hiện có $S$ rồi duyệt $s$ từ $S$ xuống $x$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, S, ok[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    ok[0] = 1;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        S += x;
        for (ll s = S; s >= x; s--)
            if (ok[s - x]) ok[s] = 1;
    }
    ll cnt = 0;
    for (ll s = 1; s <= S; s++) cnt += ok[s];
    cout << cnt << '\n';
    for (ll s = 1; s <= S; s++)
        if (ok[s]) cout << s << ' ';
    cout << '\n';
}

ChạyInput4
3 5 6 8

Output12
3 5 6 8 9 11 13 14 16 17 19 22

Độ phức tạp: $O(n S)$, với $n = 100$ và $S = 10^5$ cần khoảng $10^7$ phép tính.

Cũng theo cách này, ta đếm được số cách chia một nhóm số thành hai nhóm có tổng bằng nhau: thay phép “hoặc” bằng phép cộng số cách, và đích là nửa tổng.

IVBa lô khi khối lượng quá lớn

Nếu sức chứa $W$ tới $10^9$ thì bảng $n \times W$ không thể lập. Khi đó, nếu tổng giá trị $S = v_1 + \cdots + v_n$ nhỏ, ta đổi vai: trạng thái là giá trị, và đại lượng cần tối ưu là khối lượng. Gọi $dp_x$ là tổng khối lượng nhỏ nhất của một tập vật có tổng giá trị đúng $x$, với $dp_0 = 0$ và các ô khác $+\infty$. Mỗi vật $(w, v)$ sửa mảng với $x$ giảm dần: $dp_x \leftarrow \min(dp_x, dp_{x-v} + w)$. Đáp án là $x$ lớn nhất có $dp_x \le W$.

Ví dụBa Lô Theo Tổng Giá Trị

Đề. Có $N \le 100$ vật, vật $i$ nặng $W_i$ và có giá trị $V_i \le 1000$; ba lô chịu tổng khối lượng $C \le 10^9$. Chọn một tập vật, mỗi vật tối đa một lần, có tổng khối lượng không quá $C$ để tổng giá trị lớn nhất.

Lời giải. Bảng theo khối lượng cần $10^9$ ô, không khả thi, nhưng tổng mọi giá trị $S \le 10^5$ nhỏ. Dùng $dp_x$ như trên. Giữ khối lượng nhỏ nhất cho mỗi giá trị là đủ, vì ràng buộc chỉ là tổng khối lượng không quá $C$: tập nhẹ hơn cùng giá trị luôn thay được tập nặng hơn. Khối lượng cộng lại tới $10^{11}$ nên dùng ll, vô cực đặt $10^{18}$ để cộng thêm một khối lượng vẫn không tràn. Với ví dụ của đề, vật 1 và 2 cho giá trị $13$, nặng đúng $10$; mọi giá trị lớn hơn đều cần từ $11$ trở lên.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, C, w[105], v[105], dp[100005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> C;
    ll S = 0;
    for (ll i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
        S += v[i];
    }
    for (ll x = 1; x <= S; x++) dp[x] = 1e18;
    for (ll i = 0; i < n; i++)
        for (ll x = S; x >= v[i]; x--) dp[x] = min(dp[x], dp[x - v[i]] + w[i]);
    ll ans = 0;
    for (ll x = 0; x <= S; x++)
        if (dp[x] <= C) ans = x;
    cout << ans << '\n';
}

ChạyInput4 10
6 8
4 5
5 7
3 4

Output13

Độ phức tạp: $O(N \cdot S)$ với $S \le 10^5$, cần khoảng $10^7$ phép tính; bộ nhớ $O(S)$.

VTruy vết phương án

Cho đến giờ ta chỉ in giá trị tốt nhất. Muốn in cả tập vật được chọn, ta phải giữ cả bảng hai chiều $dp_{i,c}$, vì mảng một chiều đã ghi đè mất thông tin của các hàng trước. Từ ô $(n, W)$ đi ngược: nếu $dp_{i,c} = dp_{i-1,c}$ thì vật $i$ không cần lấy; ngược lại, vật $i$ được lấy, ta ghi lại nó rồi lùi sức chứa $c$ đi $w_i$. Danh sách ghi được theo thứ tự ngược nên in từ cuối về đầu.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, W, w[105], v[105], dp[105][1005], pick[105];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> W;
    for (ll i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for (ll i = 1; i <= n; i++)
        for (ll c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];
            if (c >= w[i]) dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i]] + v[i]);
        }
    ll cnt = 0, c = W;
    for (ll i = n; i >= 1; i--)
        if (dp[i][c] != dp[i - 1][c]) {
            pick[cnt++] = i;
            c -= w[i];
        }
    cout << dp[n][W] << '\n';
    for (ll i = cnt - 1; i >= 0; i--) cout << pick[i] << ' ';
    cout << '\n';
}

ChạyInput4 6
3 4
2 3
4 6
1 1

Output9
2 3 

Độ phức tạp: $O(nW)$ thời gian và bộ nhớ, với $n = 100$ và $W = 1000$ cần khoảng $10^5$ phép tính.

Trên ví dụ này chương trình in vật 2 và vật 3, đúng như đường truy ngược trong hình ở đầu trang. Nếu bảng quá lớn để giữ, ta chỉ lưu thêm một bit “có lấy vật $i$ ở sức chứa $c$ hay không”, nhưng vẫn là $O(nW)$ bit.