\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• Thử từng dãy con một và tính tổng khối lượng \(sum\_weight\) và tổng giá trị \(sum\_value\)

Mỗi cặp \((weight_i, value_i)\) có thể chọn hoặc là không, nên có 2 cách tất cả, với số lượng được lấy là \(x_i \in \{0/1\}\)

Gọi \(S\) là tập hợp con các vị trí \(i\) mà \(x_i = 1\) mình đang xét với độ dài \(k \in [0, n]\)

\(sum\_weight(S) = \underset{i \in S}{\Sigma} weight_i\)

\(sum\_value(S) = \underset{i \in S}{\Sigma} value_i\)

• \(res = max(sum\_value(S))\) thỏa \(sum\_weight(S) \leq W\)

• Tổng số cách chọn là \(2^n\) hay có tất cả \(2^n\) tập S cần xét nên độ phức tạp thời gian là \(\Theta(2^n)\)

Cải thiện bằng \(\color{#300000}{\text{<Nhánh cận>}}\) ta có thể bỏ các trường hợp \(sum\_weight\) đang xét lớn hơn \(W\)

Cải thiện bằng \(\color{#300000}{\text{<Quy hoạch động bitmask>}}\) ta có thể tính giá trị tiếp theo nhanh hơn từ bài toán con trước khi xét cặp \(i\)

\(\color{#300000}{\text{Hint 2 <Quy hoạch động>}}\)

• Gọi \(f[i][v]\) là khối lượng nhỏ nhất chọn được từ các túi \(a_1 \dots a_i\) với khối lượng đúng bằng \(v\)

Khởi tạo các phần tử là \(+oo\) để tiện tính giá trị nhỏ nhát

• Nhận xét:

[1] \(f[i][0] = 0 \forall i \in [0, n]\) vì khi không lấy gì \(sum\_weight = sum\_value = 0\). Hay lấy tập rỗng (\(0\) phần tử) thì không tốn gì (không tốn quá \(0\) không gian chứa)

[2] \(f[j][v] \geq f[i][v] \forall j \leq i\) vì có thể tồn tại một cách lấy khác với cùng giá trị nhưng khối lượng nhỏ hơn

[3] \(f[i][c] \leq f[i][v] \forall c \leq v\) vì việc lấy thêm một cặp nữa sẽ làm tăng khối lượng (\(weight_i > 0\))

[4] \(f[i][v]\) sẽ phụ thuộc vào \(f[i - 1][c]\) với \(c \in [0, v]\) khi xét cặp thứ \(i\) (dựa vào [2] và [3] thì \(f[i][v]\) là tối ưu tới hiện tại)

• Để tính \(f[i][v]\) ta xét cặp \((weight_i, value_i)\)

Nếu ta không chọn cặp này, hoặc không thể chọn cặp này (\(v < value_i\) thì không có balo nào có giá trị âm). Thì giá trị balo hiện tại là như trước khi xét cặp này \(f[i - 1][v]\) (theo [4])

Nếu ta chọn cặp này. Thì balo trước có giá trị đúng bằng \(v - value_i\) và thêm vào một khối lượng từ cặp \(i\) là \(weight_i\)

• Vậy ta có công thức:

\(f[i][v] = f[i - 1][v]\) với \(v < value_i\)

\(f[i][v] = min(f[i - 1][v], f[i - 1][v - value_i] + weight_i)\) với \(v \geq value_i\)

• Gọi \(sum = \underset{i \in [1, n]}{\Sigma}value_i\) là tổng các giá trị

• Kết quả bài toán là \(res = max(v)\) thỏa \(f[n][v] \leq capacity\)

Với \(v \in [0, sum]\) và \(capacity = W\) là sức chứa của ba lô

Chúng ta có thể duyệt ngược \(v = sum \rightarrow 0\) và nếu thỏa mãn bất đẳng thức \(f[n][v] \leq capacity\) thì xuất ra luôn

\(\color{#009933}{\text{Preference Accepted Code }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times sum)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n \times sum)\ \color{#7f5f3f}{\text{memory}}}}\)

const ll LINF = 1e18 + 1e9 + 1;
int main() {
    int n, k;
    cin >> n >> k;

    vector<int> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> weight[i] >> value[i];

    int sum = 0;
    for (int &x : value) sum += x;

    vector<vector<ll> > f(n + 1, vector<ll>(sum + 1, +LINF));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        f[i][0] = 0;
        for (int j = 1; j <= sum; ++j)
        {
            if (j >= value[i])
                f[i][j] = min(f[i - 1][j], f[i - 1][j - value[i]] + weight[i]);
            else 
                f[i][j] = f[i - 1][j];
        }
    }

    for (int v = sum; v-->0; )
    {
        if (f[n][v] <= k)
        {
            cout << v;
            return 0;
        }
    }            
}

\(\color{#300000}{\text{Hint 3 <Giảm chiều quy hoạch động>}}\)

• Nhận xét [4] (\(f[i][v]\) sẽ phụ thuộc vào \(f[i - 1][c]\) với \(c \in [0, v]\) và xét cặp thứ \(i\)) giúp ta giảm chiều

Vì ta chỉ quan tâm \(f[i]\) và \(f[i - 1]\) nên ta chỉ cần dùng 2 mảng \(cur[]\) (mảng đang xét ở vị trí \(i\)) và \(pre[]\) (mảng tính trước đó ở vị trí \(i - 1\))

• Việc copy mảng mới để tính mất thêm \(O(f[i].size) = O(capacity)\)

Ta có thể dùng một kĩ thuật là xét \(cur \equiv i \pmod 2\) và \(pre \equiv i - 1 \pmod 2\). Ta sẽ xét và ghi đè lên mảng \(f[cur]\) và \(f[pre]\)

• Kết quả bài toán là \(res = max(v)\) thỏa \(f[t][v] \leq capacity\)

Với \(t \equiv n \pmod 2\) và \(v \in [0, sum]\) và \(capacity = W\) là sức chứa của ba lô

Chúng ta có thể duyệt ngược \(v = sum \rightarrow 0\) và nếu thỏa mãn bất đẳng thức \(f[t][v] \leq capacity\) thì xuất ra luôn

\(\color{#009933}{\text{Preference Accepted Code }}\): Quy hoạch động

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times sum)\ \color{#7f5f3f}{\text{time}}\ ||\ O(n + sum)\ \color{#7f5f3f}{\text{memory}}}}\)

```cpp
const ll LINF = 1e18 + 1e9 + 1;
int main() {
int n, k;
cin >> n >> k;

vector<int> weight(n + 1), value(n + 1);
for (int i = 1; i <= n; ++i)
    cin >> weight[i] >> value[i];

int sum = 0;
for (int &x : value) sum += x;

vector<vector<ll> > f(2, vector<ll>(sum + 1, +LINF));
f[0][0] = 0;
for (int i = 1; i <= n; ++i)
{
    bool cur = i % 2;
    bool pre = (i + 1) % 2; /// (i - 1) % 2 co the am
    f[cur][0] = 0;
    for (int j = 1; j <= sum; ++j)
    {
        if (j >= value[i])
            f[cur][j] = min(f[pre][j], f[pre][j - value[i]] + weight[i]);
        else 
            f[cur][j] = f[pre][j];
    }
}

for (int v = sum; v-->0; )
{
    if (f[n % 2][v] <= k)
    {
        cout << v;
        return 0;
    }
}

}
````

\(\color{#9000ff}{\text{Question}}\)

• Liệu bạn có thể giải bài này trực tiếp (vừa nhận phần tử đã giải) với bộ nhớ đúng bằng mảng một chiều với độ phức tạp bộ nhớ \(O(sum)\)

Bạn đọc tham khảo ở Bài toán ba lô 1