\(\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][w]\) là giá trị lớn nhất chọn được từ các túi \(a_1 \dots a_i\) với khối lượng không quá \(w\)

• 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][w] \leq f[i][w] \forall j \leq i\) vì việc lấy thêm phần tử khi có thể (tổng không quá \(w\)) luôn làm mình có lợi hơn (vì \(value_i \geq 0\))

[3] \(f[i][c] \leq f[i][w] \forall c \leq w\) vì việc có thêm không gian chứa sẽ có thể lấy thêm phần tử tốt hơn hoặc nhiều phần tử hơn

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

• Để tính \(f[i][w]\) 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 (\(w < weight_i\) thì không có balo nào đủ chứa nó). Thì giá trị balo hiện tại là như trước khi xét cặp này \(f[i - 1][w]\) (theo [4])

Nếu ta chọn cặp này. Thì balo trước đó phải đủ chứa \(weight_i\) là các balo \(f[i][0 \dots w - weight_i]\) và ba lô giá trị lớn nhất là \(f[i][w - weight_i]\) (theo [3]) và thêm vào một giá trị từ cặp \(i\) là \(value_i\)

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

\(f[i][w] = f[i - 1][w]\) khi \(w < weight_i\)

\(f[i][w] = max(f[i - 1][w], f[i - 1][w - weight_i] + value_i)\) khi \(w \geq weight_i\)

• Kết quả bài toán là \(res = f[n][capacity]\) với \(capacity = W\) là sức chứa của ba lô

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

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;

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

    vector<vector<ll> > f(n + 1, vector<ll>(capacity + 1, 0LL));
    for (int i = 1; i <= n; ++i)
    {
        for (int w = 1; w <= capacity; ++w)
        {
            if (w >= weight[i - 1]) // neu co the chon
                f[i][w] = max(f[i - 1][w], f[i - 1][w - weight[i - 1]] + value[i - 1]);
            else
                f[i][w] = f[i - 1][w];
        }
    }

    cout << f[n][capacity];
    return 0;
}

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

• Nhận xét [4] (\(f[i][w]\) sẽ phụ thuộc vào \(f[i - 1][c]\) với \(c \in [0, w]\) 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à \(f[last][capacity]\) với \(last \equiv n \pmod 2\)

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

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

int main()
{
    int n, capacity;
    cin >> n >> capacity;

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

    vector<vector<ll> > f(2, vector<ll>(capacity + 1, 0LL));
    for (int i = 1; i <= n; ++i)
    {
        int cur = i % 2;
        int pre = (i + 1) % 2; // (i - 1) % 2 co the ra so am
        for (int w = 1; w <= capacity; ++w)
        {
            if (w >= weight[i - 1]) // neu co the chon
                f[cur][w] = max(f[pre][w], f[pre][w - weight[i - 1]] + value[i - 1]);
            else 
                f[cur][w] = f[pre][w];
        }
    }

    cout << f[n % 2][capacity];
    return 0;
}
````


---
## $\color{#300000}{\text{Hint 4 <Giải trực tiếp> <Quy hoạch động trên bộ nhớ tuyến tính>}}$


- Gọi mảng $g[w][n] = f[n][w]$ là kết quả tối ưu của việc chọn trong tập $n$ cặp đầu tiên sao cho khối lượng không quá $w$


- Nhận xét từ gợi ý giảm chiều phía trước. Việc cập nhật kết quả từ $w = 1 \rightarrow capacity$ sẽ ghi đè lên mảng quy hoạch động trước đó

> Nhưng trước khi bị ghi đè, thì chả phải $g[w][i - 1] = g[w][pre]$ hay sao (khi cập nhật mình sẽ xét nó như $g[w][i] = g[w][cur]$)


- Tuy nhiên, từ nhận xét `[3]` ($f[i][c] \leq f[i][w] \forall c \leq w$ vì việc có thêm không gian chứa sẽ có thể lấy thêm phần tử tốt hơn hoặc nhiều phần tử hơn)

> Ta có thể thấy $f[i][w]$ sẽ không cập nhật các $f[i][c]$ mà $c \in (w, capacity]$


- Nên ta sẽ duyệt ngược về từ $w = capacity \rightarrow 1$ và tính toán dựa trên một mảng duy nhất $g[w]$ (bỏ chiều $[n]$)

> Mỗi một cặp phần tử nhận vào, ta có thể tính trực tiếp ngay trên mảng $g[w]$ nên ta không cần chiều $[n]$

> Lúc này các giấ trị vẫn được cập nhật đúng từ các giá trị chưa được cập nhật trước đó

> Khi xét đến $w \geq weight_i$ thì $g[w] = max(g[w], g[w - weight_i] + value_i)$ /// g[w] trong hàm max lúc này là mảng $pre$

> Khi xét đến $w < weight_i$ thì ta chỉ cập nhật $g[w] = g[w]$ nên ta có thể break từ đoạn này và không cập nhật gì cả. Hoặc đơn giản ta chỉ chạy $w = capacity \rightarrow weight_i$

---
# $\color{#009933}{\text{Preference Accepted Code }}$: Giải trực tiếp, Quy hoạch động
# $^{^{\color{#7f5f3f}{\text{Complexity : }} O(n \times capacity)\ \color{#7f5f3f}{\text{time}}\ ||\ O(capacity)\ \color{#7f5f3f}{\text{memory}}}}$
```cpp
int main()
{
    int n, k;
    cin >> n >> k;

    vector<ll> f(k + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        int weight, value;
        cin >> weight >> value;
        for (int j = k; j >= weight; --j)
            maximize(f[j], f[j - weight] + value);
    }

    cout << f[k];
    return 0;
}