Knapsack the tutorial
Difference between en1 and en2, changed 3302 character(s)
--------------------↵

--------------------↵

<a name="TOC"></a>↵

> **Teleporter:** **[**[Previous](#status)**]** | | | **[**[Next](#statement)**]**↵

### <strong> <center style="color:red;"> Table of content </center> </strong> ↵

> This blog isnt the best but worth spending time to read it↵

| Teleporter                                                       | Description                                                                                   |↵
| :--------------------------------------------------------------- | :-------------------------------------------------------------------------------------------- |↵
| [I. STATEMENT](#statement)                                       | Taking about the problem                                                                      |↵
| [II. EXAMPLE](#example)                                          | To understand the problem better                                                              |↵
| [III. Solution for small number of element &mdash; N](#small_n)  | How much will you get in each possible subset ?                                               |↵
| [IV. Solution for small sum of weight &mdash; C[i]](#small_c)    | What is the maximum value possible when your bag is exact $W$ weight ?                        |↵
| [V. Solution for small sum of value &mdash; V[i]](#small_v)      | What is the minimum bag weight possible when it is exact $S$ sum value ?                      |↵
| [VI. Tracing for selected elements](#trace)                      | Which next state will lead to the best result ?                                               |↵
| [VII. Other solutions](#other)                                   | How to solve the problem with special condition ?                                             |↵
| [VIII. Online Algorithm](#online)                                | How to solve the problem when you need to output the result whenever you receive a new item ? |↵
| [IX. Optimizations and Heuristic](#optimize)                     | How to improve the algorithm faster, shorter, simpler, safetier or saving space               |↵
| [X. Debugging](#debug)                                           | Support you when you are in a trouble that you cant find your bug                             |↵
| [XI. Knapsack Variation and Practice Problems](#practice)        | In case you need a place to practice or submitting                                            |↵
| [XII. Blog status](#status)                                      | The current progress and contributor of this blogs                                            |↵











































































































































































































































































































































































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="statement"></a>↵

> **Teleporter:** **[**[Previous](#TOC)**]** | | | **[**[Next](#example)**]**↵

### <strong> <center style="color:red;"> I. STATEMENT </center> </strong> ↵

> Taking about the problem↵

**Problem:** During midnight, a thief breaks into a jewelry shop. There are $N$ priceful items whose value and weight are known. The item $p$ can be sold for $V_p$ money but having $C_p$ weight. There is a bag with infinity amount of space, means that any item can be pinto it while the item's value in the bag remain unchanged ! But, it can only hold **maximumly** $W$ weight.↵

**Question:** What is the value $V$ that the thief can steal from the shop.↵






































































































































































































































































































































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="example"></a>↵

> **Teleporter:** **[**[Previous](#statement)**]** | | | **[**[Next](#small_n)**]**↵

### <strong> <center style="color:red;"> II. EXAMPLE </center> </strong>↵

> To understand the problem better↵

--------------------↵

--------------------↵

- **Input**↵

```css↵
3 8↵
2 10↵
4 20↵
6 30↵
```↵

---------↵

- **Output**↵

```css↵
40↵
```↵

---------↵

- **Explanation:**↵

```css↵
There are 8 possible cases↵
{} -> 0 value, 0 weight↵
{1} -> 10 value, 2 weight↵
{2} -> 20 value, 4 weight↵
{3} -> 30 value, 6 weight↵
{1, 2} -> 30 value, 6 weight↵
{1, 3} -> 40 value, 8 weight - optimal↵
{2, 3} -> 50 value, 10 weight - invalid weight↵
{1, 2, 3} -> 60 value, 12 weight - invalid weight↵
```↵























































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

| :--- |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="small_n"></a>↵

> **Teleporter:** **[**[Previous](#example)**]** | | | **[**[Next](#small_c)**]**↵

### <strong> <center style="color:red;"> III. Solution for small number of element &mdash; N </center> </strong>↵

> How much will you get in each possible subset ?↵

-----------↵

-----------↵

##### <span style="color:green;"> A. Permutation Approach (Bad) </span> &mdash; $O(n!)$ <span style="color:green;">  time </span> &mdash; $O(n)$ <span style="color:green;"> space </span>↵

- For each possible permutation, pick elements until it weight too much↵

- The result is the maximum value sum, for which weight sum is not greater than $W$↵

----↵

<spoiler summary="Permutation Approach - O(n!) time - O(n) space">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <numeric>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    int p[n];↵
    iota(p, p + n, 0);↵

    ll res = 0;↵
    do {↵
        ll sum_weight = 0;↵
        ll sum_value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            int weight = c[p[i]];↵
            int value = v[p[i]];↵

            sum_weight += weight;↵
            sum_value += value;↵
            if (sum_weight > w) ↵
            {↵
                break;↵
            }↵
            else↵
            {↵
                maximize(res, sum_value);↵
            }↵
        }↵

    }↵
    while (next_permutation(p, p + n));↵

    cout << res;↵
    return 0;↵
}↵
```↵
</spoiler>↵

-----------↵

-----------↵


##### <span style="color:green;"> B. Bitmasking Approach (Good) </span> &mdash; $O(2^n \times n)$ <span style="color:green;">  time </span> &mdash; $O(n)$ <span style="color:green;"> space </span>↵

- Because the order isnt important, we just need to test all every possible subset↵

- The result is the maximum value sum, for which weight sum is not greater than $W$↵

<spoiler summary="Bitmasking Approach - O(2^n * n) time - O(n) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll res = 0;↵
    int lim = 1 << n;↵
    for (int mask = 0; mask < lim; ++mask)↵
    {↵
        int weight = 0;↵
        ll value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            if (mask >> i & 1)↵
            {↵
                weight += c[i];↵
                value += v[i];↵
                if (weight > w) break;↵
            }↵
        }↵

        if (weight <= w)↵
        {↵
            maximize(res, value);↵
        }↵
    }↵

    cout << res << endl;↵
    return 0;↵
}↵
```↵
</spoiler>↵

-----------↵

-----------↵


##### <span style="color:green;"> C. Meet-in-the-middle Approach (Better) </span> &mdash; $O(2^{^{\frac{n}{2}}} \times \frac{n}{2})$ <span style="color:green;">  time </span> &mdash; $O(2^{^{\frac{n}{2}}})$ <span style="color:green;"> space </span>↵

- Split the array into two halves $L$ and $R$. In each half, we will calculate every possible subsets. And in each subset we store a pair of $(value\ sum, weight\ sum)$↵

- For each element $X(value_X, weight_X) \in L$, we need to find suitable element $Y(value_Y, weight_Y) \in R$ that satisfying maximum $value_R$ and $weight_L + weight_R \leq W$↵

- Therefore, we can sort all the $R$ set by increasing weight. Let $maxval_Y = max(value_E | E \in R, weight_E \leq weight_Y)$. Then for each $X \in L$, we can find its suitable $Y$ by binary search in $O(log\ |R|)$ with $O(|R|)$ precalculation↵

<spoiler summary="Meet in the middle approach - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

struct Node ↵
{↵
    ll maxval = 0;↵

    ll value;↵
    int weight;↵
    Node (ll value = 0, int weight = 0)↵
    : value(value), weight(weight) {}↵
};↵

int n, w;↵
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)↵
{↵
    int n = c.size(); /// Important !!!↵
    int lim = 1 << n;↵
    for (int mask = 0; mask < lim; ++mask)↵
    {↵
        ll weight = 0;↵
        ll value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            if (mask >> i & 1)↵
            {↵
                weight += c[i];↵
                value += v[i];↵
                if (weight > w) break;↵
            }↵
        }↵

        if (weight <= w)↵
        {↵
            S.push_back(Node(value, weight));↵
        }    ↵
    }↵
}↵

int main()↵
{↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    int m = n / 2;↵
    vector<int> cl, cr;↵
    vector<int> vl, vr;↵
    for (int i = 0; i < n; ++i)↵
    {↵
        if (i < m)↵
        {↵
            cl.push_back(c[i]);↵
            vl.push_back(v[i]);↵
        }↵
        else ↵
        {↵
            cr.push_back(c[i]);↵
            vr.push_back(v[i]);↵
        }↵
    }↵

    vector<Node> Sl, Sr;↵
    solve(cl, vl, Sl);↵
    solve(cr, vr, Sr);↵

    sort(all(Sr), [](const Node &a, const Node &b) {↵
        return (a.weight != b.weight) ? a.weight < b.weight : a.value < b.value;↵
    });↵

    ll maxval = 0;↵
    for (Node &x : Sr)↵
    {↵
        maximize(maxval, x.value);↵
        x.maxval = maxval;↵
    }↵

    ll res = 0;↵
    for (Node &y : Sl)↵
    {↵
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )↵
        {↵
            int m = (l + r) >> 1;↵
            Node x = Sr[m];↵
            if (x.weight + y.weight <= w)↵
            {↵
                maximize(res, x.maxval + y.value);↵
                l = m + 1;↵
            }↵
            else ↵
            {↵
                r = m - 1;↵
            }↵
        }↵
    }↵

    cout << res;↵
    return 0;↵
}↵
```↵
</spoiler>↵













































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

| :--- |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="small_c"></a>↵

> **Teleporter:** **[**[Previous](#small_n)**]** | | | **[**[Next](#small_v)**]**↵

### <strong> <center style="color:red;"> IV. Solution for small sum of weight &mdash; C[i] </center> </strong>↵

> What is the maximum value possible when your bag is exact $W$ weight ?↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Recursive Dynamic Programming </span> &mdash; $O(N \times W)$ <span style="color:green;">  time </span> &mdash; $O(N \times W)$ <span style="color:green;"> space </span>↵

- Memorization:↵
 ↵
     + `f[i][s] = magic(int i, int s)` stand for using from the $ith$ items, with the total weight of $s$ that maximum value is $f[i][s]$↵

     + All $f[i][s]$ init as $-1$↵

- Base cases↵

     + If ($s > w$) then $v = -oo$ since we use more than what the bag can hold↵

     + If ($i \geq n$) then $v = 0$ since there is no available item, so no weight added into the bag↵

- Transistion↵

     + Using current item, it will be $A = magic(i + 1, s + c_i) + v_i)$ &mdash; move to next item, weight is added with $c_i$, value is increased by $v_i$↵

     + Not using current item, it will be $B = magic(i + 1, s + 0) + 0)$ &mdash; move to next item, weight is remained, value is not increased↵
    ↵
     + We want the maximum value so $magic(int\ i, int\ s) = max(A, B)$↵

- The final result: $result = magic(1, 0)$ &mdash; starting from first item with $0$ weighted bag↵

<spoiler summary="Recursive Approach - O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXW = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXW];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s > w) return -LINF; /// Using too much weight↵
    if (i > n) return 0;     /// No available item to add into the bag↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
        ↵
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item↵
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item↵
    return res;↵
}↵

int main()↵
{↵
    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    memset(f, -1, sizeof(f));↵
    cout << magic();↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> B) Iterative Dynamic Programming </span> &mdash; $O(N \times W)$ <span style="color:green;">  time </span> &mdash; $O(N \times W)$ <span style="color:green;"> space </span>↵

- Memorization:↵
 ↵
     + `f[i][s]` stand for using from the $ith$ items, with the total weight exact $s$ that maximum value is $f[i][s]$↵

     + All $f[i][s]$ init as $0$ not $-1$↵

- Base cases:↵

     + $\forall x \geq 0, f[0][x] = 0$ &mdash; using no item, hence return no value↵
     + $\forall x \geq 0, f[x][0] = 0$ &mdash; having no weight, hence no using item↵
     + $\forall x > 0, y < 0, f[x][y] = -oo$ &mdash; define it as negative infinity for easier calculation↵

- Transistion:↵

     + Using current item, $A = \underset{0 \leq t + c_i \leq s}{\underset{j \leq i}{max}}(f[j][t]) + v[i] =  \underset{0 \leq t = s - c_i}{\underset{j \leq i}{max}}(f[j][t]) + v[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$ maximum value among all previous bags added to current item↵

     + Not using current item, it will be $B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{max}}(f[j][t]) + 0 =  \underset{0 \leq t = s}{\underset{j \leq i}{max}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$ &mdash; move to next item, weight is remained, value is not increased↵
    ↵
     + We want the maximum value so $f[i][s] = max(A, B) = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$↵

- The final result: $result = \underset{0 \leq s \leq w}{max}(f[n][s])$ &mdash; starting from first item with $0$ weighted bag↵

<spoiler summary="Bad Approach - O(N^2 * W^2) time">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll res = 0;↵
    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 1; s <= w; ++s)↵
        {↵
            for (int j = 1; j < i; ++j)↵
            {↵
                for (int t = 0; t <= s; ++t)↵
                {↵
                    maximize(f[i][s], f[i][t] + 0);↵
                }↵
                ↵
                for (int t = 0; t + c[i] <= s; ++t)↵
                {↵
                    maximize(f[i][s], f[i - 1][t] + v[i]);↵
                }↵
            }↵

            maximize(res, f[i][s]);↵
        }↵
    }↵

    cout << res;↵
    return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Iterative Approach - O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 1; s <= w; ++s)↵
        {↵
            f[i][s] = f[i - 1][s];↵
            if (s >= c[i])↵
            {↵
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);↵
            }↵
        }↵
    }↵

    ll res = 0;↵
    for (int s = 0; s <= w; ++s)↵
        maximize(res, f[n][s]);↵

    cout << res;↵
    return 0;↵
}↵
```↵
</spoiler>↵


<spoiler summary="Prefixmax DP Approach - O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 1; s <= w; ++s)↵
        {↵
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);↵
            if (s >= c[i])↵
            {↵
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);↵
            }↵
        }↵
    }↵

    cout << f[n][w];↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> C) Recursive Dynamic Programming (Space optimization) </span> &mdash; $O(N \times W)$ <span style="color:green;">  time </span> &mdash; $O(N + W)$ <span style="color:green;"> space </span>↵

**A) O(2W) DP space**↵

- Observe: $\forall i > 0, f[i][x]$ depends on $f[i - 1]$ and $f[i]$ only, hence we just need 2 dp array space↵

- Define: When we calculate at **pth** element, we have $\underset{x \equiv p (mod 2)}{f[x]}$ is current dp array, $\underset{y \equiv p + 1 (mod 2)}{f[y]}$ is previous dp array↵

- Transistion: $f[i][s] = max(f[i - 1][s], f[i - 1][s - c_i] + v_i)$ equivalent to $f[x][s] = max(f[y][s], f[y][s - c_i] + v_i)$↵

<spoiler summary="Space Optimization Approach - O(NW) time - O(N + 2W) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll f[2][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 1; s <= w; ++s)↵
        {↵
            f[cur][s] = f[pre][s];↵
            if (s >= c[i])↵
            {↵
                maximize(f[cur][s], f[pre][s - c[i]] + v[i]);↵
            }↵
        }↵
    }↵

    ll res = 0;↵
    for (int s = 0; s <= w; ++s)↵
        maximize(res, f[n & 1][s]);↵

    cout << res;↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------------↵

--------------------------↵

**B) O(W) 1D &mdash; DP space**↵

- From the above algorithm, we can change the inner loop ↵

<spoiler summary="Inner Part">↵

```cpp↵
    ll f[2][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 1; s <= w; ++s)↵
            f[cur][s] = f[pre][s];↵
        ↵
        for (int s = w; s >= c[i]; --s)↵
            maximize(f[cur][s], f[pre][s - c[i]] + v[i]);↵
    }↵
```↵
</spoiler>↵

- Kinda tricky, but we only need one array, for each query $f[s]$ stand for maximum value with bag of weight $s$ upto that query.↵

<spoiler summary="Inner Part">↵

```cpp↵
    ll f[w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i) /// For each item (c[i], v[i])↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 1; s <= w; ++s) /// Unneeded loop↵
            f[s] = f[s];↵
        ↵
        for (int s = w; s >= c[i]; --s)↵
            maximize(f[s], f[s - c[i]] + v[i]);↵
    }↵
```↵
</spoiler>↵

- Notice that it is required for the second-inner-loop to iterate from $w$ downto $c_i$. Here is the reason↵

<spoiler summary="From c[i] upto w">↵

```cpp↵
        for which↵

            f[cur][s] = f[s] that updated↵
            f[pre][s] = f[s] that not update yet↵

        the part↵

            for (int s = c; s <= w; ++s)↵
                maximize(f[s], f[s - c] + v);↵

        equivalent to↵

            for (int s = c; s <= w; ++s)↵
                maximize(f[cur][s], f[cur][s - c] + v);↵
```↵
</spoiler>↵

<spoiler summary="From w downto c[i]">↵

```cpp↵
        for which↵

            f[cur][s] = f[s] that updated↵
            f[pre][s] = f[s] that not update yet↵

        the part↵

            for (int s = w; s >= c; --s)↵
                maximize(f[s], f[s - c] + v);↵

        equivalent↵

            for (int s = w; s >= c; --s)↵
                maximize(f[cur][s], f[pre][s - c] + v);↵
```↵
</spoiler>↵

- Finally, here is 1D Dynamic Programming Solution↵

<spoiler summary="Space Optimization Approach - O(NW) time - O(N + 1W) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll f[w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
        for (int s = w; s >= c[i]; --s)↵
            maximize(f[s], f[s - c[i]] + v[i]);↵

    cout << f[w];↵
    return 0;↵
}↵
```↵
</spoiler>↵














































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

| :--- |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="small_v"></a>↵

> **Teleporter:** **[**[Previous](#small_c)**]** | | | **[**[Next](#trace)**]**↵

### <strong> <center style="color:red;"> V. Solution for small sum of value &mdash; V[i] </center> </strong>↵

> What is the minimum bag weight possible when it is exact $S$ sum value ?↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Recursive Dynamic Programming </span> &mdash; $O(N \times SUM)$ <span style="color:green;">  time </span> &mdash; $O(N \times SUM)$ <span style="color:green;"> space </span>↵

- Memorization:↵
 ↵
     + `f[i][s] = magic(int i, int s)` stand for using from the $ith$ items, with the total value of $s$ that minimum weight is **exact** $f[i][s]$↵

     + All $f[i][s]$ init as $-1$↵

- Base cases↵

     + If ($s < 0$) then $v = +oo$ means we use more value than expected↵

     + If ($i > n$ and $s \neq 0$) then $v = +oo$ means there is currently no bag of exact $s$ value↵

     + If ($i > n$ and $s = 0$) then $v = 0$ means there is actually a bag of exact $s$ value↵

- Transistion↵

     + Using current item, it will be $A = magic(i + 1, s - v_i) + c_i)$ &mdash; move to next item, sum value is reduce by $v_i$, weight is added with $c_i$↵

     + Not using current item, it will be $B = magic(i + 1, s - 0) + 0)$ &mdash; move to next item, sum value is remained, weight is not increased↵
    ↵
     + We want the minimum weight so $magic(int\ i, int\ s) = min(A, B)$↵

- The final result: $result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | magic(1, s) \leq w)$ &mdash; maximum value whose weight is not greater than $W$↵

<spoiler summary="Recursive Approach - O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXSUM = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXSUM];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s < 0) return +LINF;↵
    if (i > n) return (s == 0) ? 0 : +LINF;↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
    res = +LINF;↵

    minimize(res, magic(i + 1, s - 0) + 0);↵
    minimize(res, magic(i + 1, s - v[i]) + c[i]);↵
    return res;↵
}↵

int main()↵
{↵
    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    memset(f, -1, sizeof(f));↵
    for (int res = sum; res >= 0; --res)↵
    {↵
        if (magic(1, res) <= w)↵
        {↵
            cout << res;↵
            return 0;↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> B) Iterative Dynamic Programming </span> &mdash; $O(N \times SUM)$ <span style="color:green;">  time </span> &mdash; $O(N \times SUM)$ <span style="color:green;"> space </span>↵

- Memorization:↵
 ↵
     + `f[i][s]` stand for using from the $ith$ items, with the total value of exact $s$ that maximum value is $f[i][s]$↵

     + All $f[i][s]$ init as $+oo$ not $-1$↵

- Base cases:↵

     + $\forall x \geq 0, f[0][x] = 0$ &mdash; using no item, hence return no weight↵
     + $\forall x \geq 0, f[x][0] = 0$ &mdash; having no value, hence no using item↵
     + $\forall x > 0, y < 0, f[x][y] = +oo$ &mdash; define it as negative infinity for easier calculation↵

- Transistion:↵

     + Using current item, $A = \underset{0 \leq t + v_i \leq s}{\underset{j \leq i}{min}}(f[j][t]) + c[i] =  \underset{0 \leq t = s - v_i}{\underset{j \leq i}{min}}(f[j][t]) + c[i] = \underset{0 \leq t = s - c_i}{\underset{j = i - 1}{f[j][t]}} + v[i]$ minimum weight among all previous bags added to current item↵

     + Not using current item, it will be $B = \underset{0 \leq t + 0 \leq s}{\underset{j \leq i}{min}}(f[j][t]) + 0 =  \underset{0 \leq t = s}{\underset{j \leq i}{min}}(f[j][t]) + 0 = \underset{0 \leq t = s}{\underset{j = i - 1}{f[j][t]}} + 0$ &mdash; move to next item, value is remained, weight is not increased↵
    ↵
     + We want the minimum weight so $f[i][s] = min(A, B) = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$↵

- The final result: $result = \underset{0 \leq s \leq \Sigma(v_i)}{max}(s | f[n][s] \leq w)$ &mdash;  maximum value whose weight is not greater than $W$↵

<spoiler summary="Iterative Approach - O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    ll f[n + 1][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 0; s <= sum; ++s)↵
        {↵
            f[i][s] = f[i - 1][s];↵

            if (s >= v[i])↵
            {↵
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);↵
            }↵
        }↵
    }↵

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

    return 0;↵
}↵
```↵
</spoiler>↵



--------------------↵

--------------------↵

##### <span style="color:green;"> C) Iterative Dynamic Programming (Space Optimization) </span> &mdash; $O(N \times SUM)$ <span style="color:green;">  time </span> &mdash; $O(N + SUM)$ <span style="color:green;"> space </span>↵

**A) O(2SUM) DP space**↵

- Observe: $\forall i > 0, f[i][x]$ depends on $f[i - 1]$ and $f[i]$ only, hence we just need 2 dp array space↵

- Define: When we calculate at **pth** element, we have $\underset{x \equiv p (mod 2)}{f[x]}$ is current dp array, $\underset{y \equiv p + 1 (mod 2)}{f[y]}$ is previous dp array↵

- Transistion: $f[i][s] = min(f[i - 1][s], f[i - 1][s - v_i] + c_i)$ equivalent to $f[x][s] = min(f[y][s], f[y][s - v_i] + c_i)$↵

<spoiler summary="Space Optimization Approach - O(NSUM) time - O(N + 2SUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    ll f[2][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 0; s <= sum; ++s)↵
        {↵
            f[cur][s] = f[pre][s];↵

            if (s >= v[i])↵
            {↵
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);↵
            }↵
        }↵
    }↵

    for (int res = sum; res >= 0; --res)↵
    {↵
        if (f[n & 1][res] <= w)↵
        {↵
            cout << res;↵
            return 0;↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵


--------------------------↵

--------------------------↵

**B) O(SUM) 1D &mdash; DP space**↵

- From the above algorithm, we can change the inner loop ↵

<spoiler summary="Inner Part">↵

```cpp↵
    ll f[2][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 0; s <= sum; ++s)↵
        {↵
            f[cur][s] = f[pre][s];↵

            if (s >= v[i])↵
            {↵
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);↵
            }↵
        }↵
    }↵
```↵
</spoiler>↵

- Kinda tricky, but we only need one array, for each query $f[s]$ stand for maximum value with bag of weight $s$ upto that query.↵

<spoiler summary="Inner Part">↵

```cpp↵
    ll f[2][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        bool cur = i & 1;↵
        bool pre = !cur;↵

        for (int s = 0; s <= w; ++s) /// Unneeded loop↵
            f[s] = f[s];↵
        ↵
        for (int s = sum; s >= v[i]; --s)↵
            minimize(f[s], f[s - v[i]] + c[i]);↵
    }↵
```↵
</spoiler>↵

- Notice that it is required for the second-inner-loop to iterate from $sum$ downto $v_i$. Here is the reason↵

<spoiler summary="From v[i] upto sum">↵

```cpp↵
        for which↵

            f[cur][s] = f[s] that updated↵
            f[pre][s] = f[s] that not update yet↵

        the part↵

            for (int s = v[i]; s <= sum; ++s)↵
                minimize(f[s], f[s - v[i]] + c[i]);↵

        equivalent to↵

            for (int s = v[i]; s <= sum; ++s)↵
                minimize(f[cur][s], f[cur][s - v[i]] + c[i]);↵
```↵
</spoiler>↵

<spoiler summary="From sum downto v[i]">↵

```cpp↵
        for which↵

            f[cur][s] = f[s] that updated↵
            f[pre][s] = f[s] that not update yet↵

        the part↵

            for (int s = sum; s >= v[i] --s)↵
                minimize(f[s], f[s - v[i]] + c[i]);↵

        equivalent to↵

            for (int s = sum; s >= v[i] --s)↵
                minimize(f[cur][s], f[pre][s - v[i]] + c[i]);↵
```↵
</spoiler>↵


- Finally, here is 1D Dynamic Programming Solution↵

<spoiler summary="Space Optimization Approach - O(NSUM) time - O(N + SUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    ll f[sum + 1];↵
    memset(f, +LINF, sizeof(f));↵

    f[0] = 0;↵
    for (int i = 1; i <= n; ++i)↵
        for (int s = sum; s >= v[i]; --s)↵
            minimize(f[s], f[s - v[i]] + c[i]);↵

    for (int res = sum; res >= 0; --res)↵
    {↵
        if (f[res] <= w)↵
        {↵
            cout << res;↵
            return 0;↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

















































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="trace"></a>↵

> **Teleporter:** **[**[Previous](#small_v)**]** | | | **[**[Next](#other)**]**↵

### <strong> <center style="color:red;"> VII. Tracing for selected elements </center> </strong>↵

> Which next state will lead to the best result ?↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Solution for small number of element — N  </span>↵

--------------------↵

- **A) Permutation Approach:** We will update selected elements when we see a better solution↵

<spoiler summary="Permutation - O(n!) time - O(n) space">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <numeric>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    int p[n];↵
    iota(p, p + n, 0);↵

    vector<int> selected;↵
    ll res = 0;↵
    do {↵
        bool better = false;↵
        vector<int> current;↵
        ll sum_weight = 0;↵
        ll sum_value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            int weight = c[p[i]];↵
            int value = v[p[i]];↵

            sum_weight += weight;↵
            sum_value += value;↵
            if (sum_weight > w) ↵
            {↵
                break;↵
            }↵
            else↵
            {↵
               current.push_back(p[i]);↵
                if (res < sum_value)↵
                {↵
                    better = true;↵
                    res = sum_value;↵
                }↵
            }↵
        }↵

        if (better) selected = current;↵
    }↵
    while (next_permutation(p, p + n));↵

    cout << res << '\n';↵
    sort(selected.begin(), selected.end());↵
    for (int p : selected)↵
    {↵
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **B) Bitmasking Approach:** We will update bitmask when we see a better solution↵

<spoiler summary="O(2^n) time - O(n) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll res = 0;↵
    int selected = 0;↵
    int lim = 1 << n;↵
    for (int mask = 0; mask < lim; ++mask)↵
    {↵
        ll weight = 0;↵
        ll value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            if (mask >> i & 1)↵
            {↵
                weight += c[i];↵
                value += v[i];↵
                if (weight > w) break;↵
            }↵
        }↵

        if (weight <= w)↵
        {↵
            if (res <= value)↵
            {↵
                res = value;↵
                selected = mask;↵
            }↵
        }↵
    }↵

    cout << res << '\n';↵
    for (int i = 0; i < n; ++i)↵
    {↵
        if (selected >> i & 1)↵
        {↵
            cout << i + 1 << ' ' << c[i] << ' ' << v[i] << '\n';↵
        }↵
    }↵
    return 0;↵
}↵

```↵
</spoiler>↵

--------------------↵

- **C) Meet-in-the-middle Approach:** We will update bitmask when we see a better solution **AND ON DP-CALCULATION**.↵

<spoiler summary="Bitmasking - O(2^(n/2) * (n/2)) time - O(2^(n/2)) space">↵

```cpp#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵
#include <bitset>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

struct Node ↵
{↵
    ll maxval = 0;↵
    int maxmask = 0;↵

    int mask;↵
    ll value;↵
    int weight;↵
    Node (int mask = 0, ll value = 0, int weight = 0)↵
    : mask(mask), value(value), weight(weight) {}↵
};↵

int n, w;↵
void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)↵
{↵
    int n = c.size(); /// Important !!!↵
    int lim = 1 << n;↵
    for (int mask = 0; mask < lim; ++mask)↵
    {↵
        ll weight = 0;↵
        ll value = 0;↵
        for (int i = 0; i < n; ++i)↵
        {↵
            if (mask >> i & 1)↵
            {↵
                weight += c[i];↵
                value += v[i];↵
                if (weight > w) break;↵
            }↵
        }↵

        S.push_back(Node(mask, value, weight));↵
    }↵
}↵

int main()↵
{↵
    cin >> n >> w;↵

    int c[n], v[n];↵
    for (int i = 0; i < n; ++i)↵
        cin >> c[i] >> v[i];↵

    int m = n / 2;↵
    vector<int> cl, vl;↵
    for (int i = 0; i < m; ++i)↵
    {↵
        cl.push_back(c[i]);↵
        vl.push_back(v[i]);↵
    }↵

    vector<int> cr, vr;↵
    for (int i = m; i < n; ++i)↵
    {↵
        cr.push_back(c[i]);↵
        vr.push_back(v[i]);↵
    }↵

    vector<Node> Sl, Sr;↵
    solve(cl, vl, Sl);↵
    solve(cr, vr, Sr);↵

    sort(all(Sr), [](const Node &a, const Node &b) {↵
        return (a.weight != b.weight) ? a.weight < b.weight : a.value > b.value;↵
    });↵

    ll maxval = 0;↵
    int maxmask = 0;↵
    for (Node &x : Sr)↵
    {↵
        if (maxval < x.value)↵
        {↵
            maxval = x.value;↵
            maxmask = x.mask;↵
        }↵
        x.maxval = maxval;↵
        x.maxmask = maxmask;↵
    }↵

    ll res = 0;↵
    int mask_l = 0;↵
    int mask_r = 0;↵
    for (Node &y : Sl)↵
    {↵
        for (int l = 0, r = int(Sr.size()) - 1; l <= r; )↵
        {↵
            int m = (l + r) >> 1;↵
            Node x = Sr[m];↵
            if (x.weight + y.weight <= w)↵
            {↵
                if (res < x.maxval + y.value)↵
                {↵
                    res = x.maxval + y.value;↵
                    mask_l = y.mask;↵
                    mask_r = x.maxmask;↵
                }↵
                l = m + 1;↵
            }↵
            else ↵
            {↵
                r = m - 1;↵
            }↵
        }↵
    }↵

    vector<int> selected;↵
    for (int i = 0; i < m; ++i)↵
        if (mask_l >> i & 1)↵
            selected.push_back(i);↵

    for (int i = 0; i < n - m; ++i)↵
        if (mask_r >> i & 1)↵
            selected.push_back(i + m);↵

    cout << res << '\n';↵
    cout << selected.size() << '\n';↵
    for (int p : selected)↵
    {↵
        cout << p + 1 << ' ' << c[p] << ' ' << v[p] << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> B) Solution for small sum of weight — C[i]   </span>↵
 ↵
--------------------↵

- **A) Recursive Dynamic Programming:** Starting from $(i = 0, s = 0)$, we already have $magic(i,s)$ return the best result, $magic(i + 1,s + 0) + 0)$ or/and $magic(i + 1, s + c[i]) + v[i]$ will be the best result↵

<spoiler summary="Trace cases">↵

- $magic(i,s) = magic(i + 1,s + c[i]) + v[i])$ take this element will lead to the best result↵

- $magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s + c[i])+ v[i]$ take this element wont lead to the best result↵

- $magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s + c[i])+ v[i]$ either you take or not, you will find best result↵

- When $magic(i, s) = magic(X, Y)$, trace to next state $(i = X, s = Y)$↵

- When $magic(i, s) = magic(X, Y) = magic(P, Q)$, you can either trace to next state $(i = X, s = Y)$ or $(i = P, s = Q)$↵


</spoiler>↵


<spoiler summary="Recursive DP - O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXW = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXW];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s > w) return -LINF; /// Using too much weight↵
    if (i > n) return 0;     /// No available item to add into the bag↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
        ↵
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item↵
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item↵
    return res;↵
}↵

vector<int> selected;↵
void trace(int i = 1, int s = 0)↵
{↵
    if (s > w) return ;↵
    if (i > n) return ;↵

    ll res = magic(i, s);↵
    if (res == magic(i + 1, s + 0) + 0)↵
    {↵
        return trace(i + 1, s + 0);↵
    }↵
    else ↵
    {↵
        selected.push_back(i);↵
        return trace(i + 1, s + c[i]);↵
    }↵
}↵

int main()↵
{↵
    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    memset(f, -1, sizeof(f));↵
    cout << magic() << '\n';↵

    trace();↵
    cout << selected.size() << '\n';↵
    for (int p : selected)↵
    {↵
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **B) Iterative Dynamic Programming:**↵

<spoiler summary="Prefixmax Iterative DP - O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 1; s <= w; ++s)↵
        {↵
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);↵
            if (s >= c[i])↵
            {↵
                maximize(f[i][s], f[i - 1][s - c[i]] + v[i]);↵
            }↵
        }↵
    }↵

    vector<int> selected;↵
    for (int i = n, s = w; i >= 1 && s >= 1; )↵
    {↵
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])↵
        {↵
            selected.push_back(i);↵
            s -= c[i];↵
            i -= 1;↵
            continue;↵
        }↵

        if (f[i][s - 1] > f[i - 1][s])↵
        {↵
            --s;↵
        }↵
        else /// f[i][s] = f[i - 1][s]↵
        {↵
            --i;↵
        }↵
    }↵

    cout << f[n][w] << '\n';↵
    cout << selected.size() << '\n';↵
    for (int p : selected)↵
    {↵
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **C) Iterative Dynamic Programming (Space Optimization):** ↵

<spoiler summary="Explanation">↵

- The idea is based on [user:Lusterdawn,2021-03-06]'s explanation and [user:jiangly,2021-03-06]'s solution↵

- Let $calc(*f, l, r)$ is the function that calculate the answer for items $l, l + 1, \dots, r$ with $*f$ the 1D memorization table↵

- For convention, let $calc$ return the value of $min(w, \overset{r}{\underset{i = l}{\Sigma}} c_i)$ &mdash; maximal possible weight created↵

- First we calculate $calc(*f, 1, n)$, after having the maximal value of the whole items, we can find the minimal weight that return such value. Or $weight\_used = min(p | f[p] = res)$↵

- Let $trace(s, l, r)$ is the function that tracing for all elements, whose sum weight equal $s$ and sum value is max↵

- If $(l = r)$, we will consider to select this item or not. (This item is selected when $s = c_l$)↵

- Split the items into two halves: $[l, m]$ and $(m, r]$ and then calculate DP: $sleft = calc(*L, l, m + 0)$ and $sright = calc(*R, m + 1, r)$↵

- We find such $pleft$ and $pright$ satisfy $pleft + pright = s$ that returning $max(L[pleft] + R[pright])$. Then we trace from $trace(pleft, l, m + 0)$ to $trace(pright, m + 1, r)$ (ordered selected item)↵

</spoiler>↵

<spoiler summary="Code">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

const int LIM_N = 111;↵
const int LIM_W = 1e6 + 16;↵

int n, w;↵
int c[LIM_N], v[LIM_N];↵
ll f[LIM_W];↵

int calc(ll *f, int l = 1, int r = n)↵
{↵
ll upper = 0;↵
for (int i = l; i <= r; ++i)↵
upper += c[i];↵

minimize(upper, (ll)w);↵
for (int s = 0; s <= upper; ++s)↵
f[s] = 0;↵

for (int i = l; i <= r; ++i)↵
for (int s = upper; s >= c[i]; --s)↵
maximize(f[s], f[s - c[i]] + v[i]);↵

return upper;↵
}↵

ll L[LIM_W], R[LIM_W];↵
vector<int> selected;↵
void trace(int s = w, int l = 1, int r = n)↵
{↵
if (l == r)↵
{↵
if (s == c[l])↵
{↵
selected.push_back(l);↵
}↵

return ;↵
}↵

int m = (l + r) >> 1;↵
int sleft  = calc(L, l, m + 0);↵
int sright = calc(R, m + 1, r);↵

ll mx = -1;↵
int pleft = 0;↵
int pright = s;↵
for (int v = max(0, s - sright); v <= min(s, sleft); ++v)↵
{↵
if (mx < L[v] + R[s - v])↵
{↵
mx = L[v] + R[s - v];↵
pleft = v;↵
pright = s - v;↵
}↵
}↵

trace(pleft , l, m + 0);↵
trace(pright, m + 1, r);↵
}↵

int main()↵
{↵
cin >> n >> w;↵
for (int i = 1; i <= n; ++i)↵
cin >> c[i] >> v[i];↵

calc(f);↵
ll res = f[w];↵
int weight_used = max_element(f, f + w + 1) - f;↵

trace(weight_used); ↵
cout << res << '\n'; ↵
cout << selected.size() << '\n';↵
for (int p : selected)↵
{↵
    cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> C) Solution for small sum of value — V[i] </span>↵
 ↵
--------------------↵

- **A) Recursive Dynamic Programming:** Starting from $(i = 0, s = res)$, we already have $magic(i,s)$ return the best result, $magic(i + 1,s + 0) + 0)$ or/and $magic(i + 1, s - v[i]) + c[i]$ will be the best result↵

<spoiler summary="Trace cases">↵

- $magic(i,s) = magic(i + 1,s - v[i]) + c[i])$ take this element will lead to the best result↵

- $magic(i,s) = magic(i + 1,s + 0) + 0) \neq magic(i + 1, s - v[i]) + c[i]$ take this element wont lead to the best result↵

- $magic(i,s) = magic(i + 1,s + 0) + 0) = magic(i + 1, s - v[i]) + c[i]$ either you take or not, you will find best result↵

- When $magic(i, s) = magic(X, Y)$, trace to next state $(i = X, s = Y)$↵

- When $magic(i, s) = magic(X, Y) = magic(P, Q)$, you can either trace to next state $(i = X, s = Y)$ or $(i = P, s = Q)$↵

</spoiler>↵

<spoiler summary="Recursive DP - O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXSUM = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXSUM];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s < 0) return +LINF;↵
    if (i > n) return (s == 0) ? 0 : +LINF;↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
    res = +LINF;↵

    minimize(res, magic(i + 1, s - 0) + 0);↵
    minimize(res, magic(i + 1, s - v[i]) + c[i]);↵
    return res;↵
}↵

vector<int> selected;↵
void trace(int i = 1, int s = 0)↵
{↵
    if (s < 0) return ;↵
    if (i > n) return ;↵

    ll res = magic(i, s);↵
    if (res == magic(i + 1, s + 0) + 0)↵
    {↵
        return trace(i + 1, s + 0);↵
    }↵
    else ↵
    {↵
        selected.push_back(i);↵
        return trace(i + 1, s - v[i]);↵
    }↵
}↵

int main()↵
{↵
    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    memset(f, -1, sizeof(f));↵
    for (int res = sum; res >= 0; --res)↵
    {↵
        if (magic(1, res) <= w)↵
        {↵
            trace(1, res);↵
            ↵
            cout << res << '\n';↵
            cout << selected.size() << '\n';↵
            for (int p : selected)↵
            {↵
                cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
            }↵
            return 0;↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **B) Iterative Dynamic Programming:** ↵

<spoiler summary="Iterative DP - O(NSUM) time - O(NSUM) space">↵


```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    int c[n + 1], v[n + 1];↵
    for (int i = 1; i <= n; ++i)↵
        cin >> c[i] >> v[i];↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
        sum += v[i];↵

    ll f[n + 1][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 0; s <= sum; ++s)↵
        {↵
            f[i][s] = f[i - 1][s];↵

            if (s >= v[i])↵
            {↵
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);↵
            }↵
        }↵
    }↵

    int res = sum;↵
    while (f[n][res] > w) --res;↵
    ↵
    vector<int> selected;↵
    for (int i = n, s = res; i >= 1 && s >= 1; )↵
    {↵
        if (f[i][s] == f[i - 1][s - v[i]] + c[i])↵
        {↵
            selected.push_back(i);↵
            s -= v[i];↵
            i -= 1;↵
        }↵
        else ↵
        {↵
            --i;↵
        }↵
    }↵

    cout << res << '\n';↵
    cout << selected.size() << '\n';↵
    for (int p : selected)↵
    {↵
        cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **C) Iterative Dynamic Programming (Space Optimization):** ↵

<spoiler summary="Explanation">↵


- Let $calc(*f, l, r)$ is the function that calculate the answer for items $l, l + 1, \dots, r$ with $*f$ the 1D memorization table↵

- For convention, let $calc$ return the value of $\overset{r}{\underset{i = l}{\Sigma}} v_i$ &mdash; maximal possible value created↵

- First we calculate $calc(*f, 1, n)$, after having the minimal weight of the whole items, we can find the maximal value that return such weight. Or $res = max(p | f[p] \leq w)$↵

- Let $trace(s, l, r)$ is the function that tracing for all elements, whose sum value equal $s$ and sum weight is min↵

- If $(l = r)$, we will consider to select this item or not. (This item is selected when $s = v_l$)↵

- Split the items into two halves: $[l, m]$ and $(m, r]$ and then calculate DP: $sleft = calc(*L, l, m + 0)$ and $sright = calc(*R, m + 1, r)$↵

- We find such $pleft$ and $pright$ satisfy $pleft + pright = s$ that returning $min(L[pleft] + R[pright])$. Then we trace from $trace(pleft, l, m + 0)$ to $trace(pright, m + 1, r)$ (ordered selected item)↵

</spoiler>↵

<spoiler summary="Code">↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

const int LIM_N = 111;↵
const int LIM_S = 1e6 + 16;↵

int n, w;↵
int c[LIM_N], v[LIM_N];↵
ll f[LIM_S + 1];↵

int calc(ll *f, int l = 1, int r = n)↵
{↵
int upper = 0;↵
for (int i = l; i <= r; ++i)↵
upper += v[i];↵

f[0] = 0;↵
for (int s = upper; s >= 1; --s)↵
f[s] = +LINF;↵

for (int i = l; i <= r; ++i)↵
for (int s = upper; s >= v[i]; --s)↵
minimize(f[s], f[s - v[i]] + c[i]);↵

return upper;↵
}↵

vector<int> selected;↵
ll L[LIM_S + 1], R[LIM_S + 1];↵
void trace(int s = LIM_S, int l = 1, int r = n)↵
{↵
if (l == r)↵
{↵
if (s == v[l])↵
{↵
selected.push_back(l);↵
} ↵

return ;↵
}↵

int m = (l + r) >> 1;↵
int sleft  = calc(L, l, m + 0);↵
int sright = calc(R, m + 1, r);↵

int mn = +INF;↵
int pleft = 0;↵
int pright = s;↵
for (int v = max(0, s - sright); v <= min(s, sleft); ++v)↵
{↵
if (mn > L[v] + R[s - v])↵
{↵
mn = L[v] + R[s - v];↵
pleft = v;↵
pright = s - v;↵
}↵
}↵

trace(pleft , l, m + 0);↵
trace(pright, m + 1, r);↵
}↵

int main()↵
{↵
cin >> n >> w;↵
for (int i = 1; i <= n; ++i)↵
cin >> c[i] >> v[i];↵

int res = calc(f);↵
while (f[res] > w) --res;↵
trace(res);↵

int ans = 0;↵
for (int p : selected)↵
ans += v[p];↵

cout << ans;↵
// cout << res << '\n';↵
// cout << selected.size() << '\n';↵
// for (int p : selected)↵
// {↵
//  cout << p << ' ' << c[p] << ' ' << v[p] << '\n';↵
// }↵

return 0;↵
}↵
```↵
</spoiler>↵
















































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="other"></a>↵

> **Teleporter:** **[**[Previous](#trace)**]** | | | **[**[Next](#online)**]**↵

### <strong> <center style="color:red;"> VII. Other solutions </center> </strong>↵

> How to solve the problem with special condition ?↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Fractional Knapsack & Greedy Approach  </span>↵

--------------------↵

- On progress...↵

























































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="online"></a>↵

> **Teleporter:** **[**[Previous](#other)**]** | | | **[**[Next](#optimize)**]**↵

### <strong> <center style="color:red;"> VIII. Online Algorithm </center> </strong>↵

> How to solve the problem when you need to output the result whenever you receive a new item ?↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Solution for small number of element — N </span>↵



--------------------↵

- **A)** Permutation Approach: Really not worth being used thought it is possible to optimize it↵

--------------------↵

- **B)** Bitmasking Approach: ↵


<spoiler summary="Explanation">↵

- For the $ith$ query, input the $ith$ element and iterating all bitmasks with **exactly** $ith$ bits↵

- Optimization (DP bitmask): Effective and reduce $O(n)$ calculating time with the exchange of $O(2^N)$ space↵
</spoiler>↵


<spoiler summary="Bitmasking Approach - O(2^N * N) time - O(n) space">↵

```cpp  ↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    ll res = 0;↵
    ll c[n], v[n];↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        cin >> c[i] >> v[i];↵
        int L = 1 << i;↵
        int R = 1 << (i + 1);↵
        for (int mask = L; mask < R; ++mask)↵
        {↵
            ll weight = 0;↵
            ll value = 0;↵
            for (int j = 1; j <= i; ++j)↵
            {↵
                if (mask >> j & 1)↵
                {↵
                    weight += c[j];↵
                    value += v[j];↵
                    if (weight > w) break;↵
                }↵
            }↵

            if (weight <= w)↵
            {↵
                maximize(res, value);↵
            }↵
        }↵

        cout << res << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵


<spoiler summary="DP Bitmask Approach - O(2^N) time - O(2^N) space">↵

```cpp  ↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

const int LIM = 1 << 20;↵
ll dpc[LIM], dpv[LIM];↵
int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    ll res = 0;↵
    for (int i = 0; i < n; ++i)↵
    {↵
        ll c, v;↵
        cin >> c >> v;↵
        for (int mask = (1 << i); mask < (1 << (i + 1)); ++mask)↵
        {↵
            dpc[mask] = dpc[mask ^ (1 << i)] + c;↵
            dpv[mask] = dpv[mask ^ (1 << i)] + v;↵
            if (dpc[mask] <= w)↵
                maximize(res, dpv[mask]);↵
        }↵
        cout << res << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵


--------------------↵

- **C)** Iterating Deque Approach:↵

<spoiler summary="Explanation">↵

- Let assume each item in deque is one way to fill up the bag with exact $weight$ and $value$↵

- For the $ith$ query, we will input the $ith$ item, then iterating for each element $e$ in deque to add to deque a new item that is the sum of $ith$ item and $e$ item↵

- Branch and bound (Eliminate all item whose weight > w) &mdash; Effective in normal &mdash; Highly effective when randomly generating weight↵

- Branch and bound (Minimizing weight / maximizing value) &mdash; Not recommended to use &mdash; The good thing is when one branch is used, it would eliminate $O(2^k)$ cases &mdash; The bad thing is it increases both theoretical and practical time and space complexity significantly↵

</spoiler>↵

<spoiler summary="Deque approach with little optimization - O(min(W, 2^N)) time - O(2^N) space">↵

```cpp  ↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cstdio>↵
#include <cmath>↵
#include <deque>↵

using namespace std;↵

void file(const string FILE = "Test")↵
{↵
    freopen((FILE + ".INP").c_str(), "r", stdin);↵
    freopen((FILE + ".OUT").c_str(), "w", stdout);↵
}↵

char __;↵
template<typename T>↵
void getUnsign(T &x)↵
{↵
    while (__ = getchar(), __ < '0' || __ > '9');↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵
}↵

template<typename T>↵
void getSigned(T &x)↵
{↵
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));↵
    bool sign(__ == '-');↵
    if (sign) __ = getchar();↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵

    if (sign) x = -x;↵
}↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
typedef pair<int, int> pi;↵

const int LIM = 0;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

struct item ↵
{↵
    ll weight;↵
    ll value;↵
    item (ll weight = 0, ll value = 0)↵
    : weight(weight), value(value) {}↵

    void operator += (const item &other)↵
    {↵
        weight += other.weight;↵
        value += other.value;↵
    }↵
};↵

int main()↵
{↵
int n;↵
    ll w;↵
cin >> n >> w;↵

    ll res = 0;↵
    deque<item> S;↵
    S.push_back(item(0, 0));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        ll c, v;↵
        cin >> c >> v;↵
        if (c > w) continue;↵

        deque<item> T;↵
        for (item e : S)↵
        {↵
            e += item(c, v);↵
            if (e.weight <= w)↵
            {↵
                T.push_back(e);↵
                maximize(res, e.value);↵
            }↵
        }↵

        for (const item &e : T)↵
            S.push_back(e);↵

        cout << res << '\n';↵
    }↵
    ↵
return 0;↵
}↵
```↵
</spoiler>↵


<spoiler summary="Deque approach with bad optimization - O(min(W, 2^N * N)) time - O(2^N * N) space">↵

```cpp  ↵

#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cstdio>↵
#include <cmath>↵
#include <deque>↵
#include <map>↵

using namespace std;↵

void file(const string FILE = "Test")↵
{↵
    freopen((FILE + ".INP").c_str(), "r", stdin);↵
    freopen((FILE + ".OUT").c_str(), "w", stdout);↵
}↵

char __;↵
template<typename T>↵
void getUnsign(T &x)↵
{↵
    while (__ = getchar(), __ < '0' || __ > '9');↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵
}↵

template<typename T>↵
void getSigned(T &x)↵
{↵
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));↵
    bool sign(__ == '-');↵
    if (sign) __ = getchar();↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵

    if (sign) x = -x;↵
}↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
typedef pair<int, int> pi;↵

const int LIM = 0;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

struct item ↵
{↵
    ll weight;↵
    ll value;↵
    item (ll weight = 0, ll value = 0)↵
    : weight(weight), value(value) {}↵

    void operator += (const item &other)↵
    {↵
        weight += other.weight;↵
        value += other.value;↵
    }↵
};↵

map<ll, ll> minC;↵
map<ll, ll> maxV;↵
bool update(ll &c, ll &v)↵
{↵
    bool ok = false;↵
    if (minC.count(v) == false || minC[v] > c)↵
    {↵
        minC[v] = c;↵
        ok = true;↵
    }↵

    if (maxV.count(c) == false || maxV[c] < v)↵
    {↵
        maxV[c] = v;↵
        ok = true;↵
    }↵

    return ok;↵
}↵


int main()↵
{↵
int n;↵
    ll w;↵
cin >> n >> w;↵

    ll res = 0;↵
    deque<item> S;↵

    minC[0] = 0;↵
    maxV[0] = 0;↵
    S.push_back(item(0, 0));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        ll c, v;↵
        cin >> c >> v;↵
        if (c > w) continue;↵

        deque<item> T;↵
        for (item e : S)↵
        {↵
            e += item(c, v);↵
            if (e.weight > w) continue;↵
            if (update(e.weight, e.value))↵
            {↵
                T.push_back(e);↵
                maximize(res, e.value);↵
            }↵
        }↵

        for (const item &e : T)↵
            S.push_back(e);↵

        cout << res << '\n';↵
    }↵
    ↵
return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **D)** Recursive Approach:↵

<spoiler summary="Explanation">↵

- Let $f(i, s)$ is the answer for first $i$ items and limited by $s$ weight↵

- Base cases:↵

     + $s < 0$ means we use more weight then required, hence return a bag with negative infinity value↵

     + $i = 0$ and $s \geq 0$ means no item left, hence return an empty bag with 0 value↵

- Transistion:↵

     + $f(i - 1, s)$ = max value when not use this item↵

     + $f(i - 1, s - c_i) + v_i$ = max value when use this item↵

     + $f(i, s) = max(f(i - 1, s), f(i - 1, s - c_i) + v_i)$↵

- Optimization: ↵

     + We can add a branch and bound that if prefix sum of weight is already smaller then we can return prefix sum of value.↵
        ↵
     + This will make your algorithm faster by $O(2^k)$ for $k = max(p | \overset{p}{\underset{t = 1}{\Sigma}}(c_t) \leq w)$↵
        ↵
</spoiler>↵




<spoiler summary="Recursive Approach - O(min(W, 2^N)) time - O(N) space">↵

```cpp  ↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cstdio>↵
#include <cmath>↵
#include <deque>↵

using namespace std;↵

void file(const string FILE = "Test")↵
{↵
    freopen((FILE + ".INP").c_str(), "r", stdin);↵
    freopen((FILE + ".OUT").c_str(), "w", stdout);↵
}↵

char __;↵
template<typename T>↵
void getUnsign(T &x)↵
{↵
    while (__ = getchar(), __ < '0' || __ > '9');↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵
}↵

template<typename T>↵
void getSigned(T &x)↵
{↵
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));↵
    bool sign(__ == '-');↵
    if (sign) __ = getchar();↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵

    if (sign) x = -x;↵
}↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
typedef pair<int, int> pi;↵

const int LIM = 25;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n;↵
ll w;↵
ll c[LIM], v[LIM];↵
ll solve(int i, ll s)↵
{↵
    if (s < 0) return -LINF;↵
    if (i == 0) return 0;↵

    ll res = 0;↵
    maximize(res, solve(i - 1, s));↵
    maximize(res, solve(i - 1, s - c[i]) + v[i]);↵
    return res;↵
}↵

int main()↵
{↵
    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        cin >> c[i] >> v[i];↵
        cout << solve(i, w) << '\n';↵
    }↵
return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Recursive Approach with optimization - O(min(W, 2^N / 2^K)) time - O(N) space">↵

```cpp  ↵
#include <algorithm>↵
#include <iostream>↵
#include <cstring>↵
#include <vector>↵
#include <cstdio>↵
#include <cmath>↵
#include <deque>↵

using namespace std;↵

void file(const string FILE = "Test")↵
{↵
    freopen((FILE + ".INP").c_str(), "r", stdin);↵
    freopen((FILE + ".OUT").c_str(), "w", stdout);↵
}↵

char __;↵
template<typename T>↵
void getUnsign(T &x)↵
{↵
    while (__ = getchar(), __ < '0' || __ > '9');↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵
}↵

template<typename T>↵
void getSigned(T &x)↵
{↵
    while (__ = getchar(), __ != '-' && (__ < '0' || __ > '9'));↵
    bool sign(__ == '-');↵
    if (sign) __ = getchar();↵
 ↵
    x = (__ - '0');↵
    while (__ = getchar(), __ >= '0' && __ <= '9')↵
        x = (x << 3) + (x << 1) + (__ - '0');↵

    if (sign) x = -x;↵
}↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

#define all(x) (x).begin(), (x).end()↵
typedef long long ll;↵
typedef pair<int, int> pi;↵

const int LIM = 25;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n;↵
ll w;↵
ll c[LIM], psc[LIM];↵
ll v[LIM], psv[LIM];↵
ll solve(int i, ll s)↵
{↵
    if (s >= psc[i]) return psv[i];↵
    if (s < 0) return -LINF;↵
    if (i == 0) return 0;↵

    ll res = 0;↵
    maximize(res, solve(i - 1, s));↵
    maximize(res, solve(i - 1, s - c[i]) + v[i]);↵
    return res;↵
}↵

int main()↵
{↵
    cin >> n >> w;↵

    psc[0] = psv[0] = 0;↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        cin >> c[i] >> v[i];↵
        psc[i] = psc[i - 1] + c[i];↵
        psv[i] = psv[i - 1] + v[i];↵
        cout << solve(i, w) << '\n';↵
    }↵
return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **E)** Meet in the middle approach: On the progress...↵

--------------------↵

--------------------↵

##### <span style="color:green;"> B) Solution for small sum of weight — C[i]  </span>↵
 ↵
--------------------↵

- **A) Recursive Dynamic Programming:** ↵

<spoiler summary="What have changed from the orginal ?">↵

Let $f[0][s]$ be the end state instead of $f[n][w]$↵

Convert the transistion to $magic(i, s) \rightarrow magic(i - 1, s)$↵

For the $ith$ item, the answer right now is $magic(i, s)$ and here we done↵
</spoiler>↵

<spoiler summary="O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXW = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXW];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s > w) return -LINF; /// Using too much weight↵
    if (i == 0) return 0;     /// No available item to add into the bag↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
        ↵
    maximize(res, magic(i - 1, s + 0) + 0);       /// Not using this item↵
    maximize(res, magic(i - 1, s + c[i]) + v[i]); /// Using this item↵
    return res;↵
}↵

int main()↵
{↵
    memset(f, -1, sizeof(f));↵

    cin >> n >> w;↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        cin >> c[i] >> v[i];↵
        cout << magic(i, 0) << '\n';↵
    }↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **B) Iterative Dynamic Programming:** ↵


<spoiler summary="What have changed from the orginal ?">↵

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.↵

The answer is ofcourse $f[i][w]$ &mdash; upto the $ith$ item↵
</spoiler>↵

<spoiler summary="O(NW) time - O(NW) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        int c, v;↵
        cin >> c >> v;↵

        for (int s = 1; s <= w; ++s)↵
        {↵
            f[i][s] = max(f[i][s - 1], f[i - 1][s]);↵
            if (s >= c)↵
            {↵
                maximize(f[i][s], f[i - 1][s - c] + v);↵
            }↵
        }↵

        cout << f[i][w] << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **C) Iterative Dynamic Programming (Space Optimization):** ↵


<spoiler summary="What have changed from the orginal ?">↵

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.↵

The answer is ofcourse $f[w]$ &mdash; upto the $ith$ item↵
</spoiler>↵

<spoiler summary="O(NW) time - O(W) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    ll f[w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        int c, v;↵
        cin >> c >> v;↵

        for (int s = w; s >= c; --s)↵
            maximize(f[s], f[s - c] + v);↵
    ↵
        cout << f[w] << '\n';↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> C) Solution for small sum of value — V[i]  </span>↵


--------------------↵

- **A) Recursive Dynamic Programming:** ↵

<spoiler summary="What have changed from the orginal ?">↵

Let $f[0][s]$ be the end state instead of $f[n][w]$↵

Convert the transistion to $magic(i, s) \rightarrow magic(i - 1, s)$↵

For the $ith$ item, the answer right now is $result = max(k\ |\ magic(i, k) \leq w$↵

Break the loop after the answer each query is found↵
</spoiler>↵

<spoiler summary="O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int MAXN = 101;↵
const int MAXSUM = 101010;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

int n, w;↵
int c[MAXN];↵
int v[MAXN];↵
ll f[MAXN][MAXSUM];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s < 0) return +LINF;↵
    if (i == 0) return (s == 0) ? 0 : +LINF;↵

    ll &res = f[i][s];↵
    if (res != -1) return res;↵
    res = +LINF;↵

    minimize(res, magic(i - 1, s - 0) + 0);↵
    minimize(res, magic(i - 1, s - v[i]) + c[i]);↵
    return res;↵
}↵

int main()↵
{↵
    cin >> n >> w;↵

    int sum = 0;↵
    memset(f, -1, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        cin >> c[i] >> v[i];↵

        sum += v[i];↵
        for (int res = sum; res >= 0; --res)↵
        {↵
            if (magic(i, res) <= w)↵
            {↵
                cout << res << '\n';↵
                break;↵
            }↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **B) Iterative Dynamic Programming:** ↵


<spoiler summary="What have changed from the orginal ?">↵

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.↵

Declare the dp array globally with limit size↵

The answer is ofcourse $res = max(k\ |\ f[i][k]) \leq w$ &mdash; upto the $ith$ item↵

Break the loop after the answer each query is found↵
</spoiler>↵

<spoiler summary="O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵
#include <vector>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
const int LIMN = 100;↵
const int LIMSUM = 1e5 + 15;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

ll f[LIMN][LIMSUM];↵
int main()↵
{↵
    int n, w;↵
    cin >> n >> w;↵

    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        int c, v;↵
        cin >> c >> v;↵

        sum += v;↵
        for (int s = sum; s >= 0; --s)↵
        {↵
            f[i][s] = f[i - 1][s];↵

            if (s >= v)↵
            {↵
                minimize(f[i][s], f[i - 1][s - v] + c);↵
            }↵
        }↵

        for (int res = sum; res >= 0; --res)↵
        {↵
            if (f[i][res] <= w)↵
            {↵
                cout << res << '\n';↵
                break;↵
            }↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵

--------------------↵

- **C) Iterative Dynamic Programming (Space Optimization):** ↵


<spoiler summary="What have changed from the orginal ?">↵

Instead of input the whole array then solve it, we input each single line one by one then we make a loop over it.↵

Declare the dp array globally with limit size↵

The answer is ofcourse $res = max(k\ |\ f[k]) \leq w$ &mdash; upto the $ith$ item↵

Break the loop after the answer each query is found↵
</spoiler>↵

<spoiler summary="O(NSUM) time - O(NSUM) space">↵

```cpp↵
#include <iostream>↵
#include <cstring>↵
#include <cmath>↵

using namespace std;↵

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }↵
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }↵

typedef long long ll;↵
const int LIM = 1e6 + 16;↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = 0x3f3f3f3f3f3f3f3f;↵
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====↵

ll f[LIM];↵
int main()↵
{↵
    int q, w;↵
    cin >> q >> w;↵

    memset(f, +LINF, sizeof(f));↵
    f[0] = 0;↵

    int sum = 0;↵
    while (q-->0) /// For each query↵
    {↵
        int c, v;↵
        cin >> c >> v;↵

        sum += v;↵
        for (int s = sum; s >= v; --s)↵
            minimize(f[s], f[s - v] + c);↵

        ↵
        for (int res = sum; res >= 0; --res)↵
        {↵
            if (f[res] <= w)↵
            {↵
                cout << res << '\n';↵
                break;↵
            }↵
        }↵
    }↵

    return 0;↵
}↵
```↵
</spoiler>↵






























































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="optimize"></a>↵

> **Teleporter:** **[**[Previous](#online)**]** | | | **[**[Next](#debug)**]**↵

### <strong> <center style="color:red;"> IX. Optimizations and Heuristic </center> </strong>↵

> How to improve the algorithm faster, shorter, simpler, safetier or saving space↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Filtering the array </span>↵

--------------------↵

- **1)** Split items into 2 types, whose weight less than $W$ and the rest↵

<spoiler summary="Hint">↵

+ All items whose weight bigger than the bag limit will be ignored↵
+ All items whose weight equal the bag limit, we have the max value $V_1$↵
+ All items whose weight less than the bag limit, we calculate it like above and have the max value $V_2$↵
+ The result will be $res = max(V_1, V_2)$↵
+ Highly effective for $type\ III$ knapsack whose testcases randomly generated that item weight can be much bigger than bag limit↵
+ Less effective in normal testcases↵
</spoiler>↵

--------------------↵

- **2)** Compressed the array↵

<spoiler summary="Hint">↵

+ Lets $F(C_p, V_p) = $ number of existance of $(C_p, V_p)$ in the array↵
+ Array with $F(C_p, V_p) = X > 2$ and $F(2C_p, 2V_p) = Y$ can be converted to $F(C_p, V_p) = X - 2$ and $F(2C_p, 2V_p) + 1)$ without changing the result↵
+ Significant effective for testcases having many duplicated items in arrays↵
+ Having the same idea. Significant effective when $\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$ we can have only $O(\sqrt{X})$ unique weight, no item whose weight is $C$ appeared more than twice↵
+ Having the same idea. Significant effective when $\underset{p = 1}{\overset{n}{\Sigma}} C_p \approx X$ we can have only $O(\sqrt{X})$ unique value, , no item whose value is $V$ appeared more than twice↵
</spoiler>↵















































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="debug"></a>↵

> **Teleporter:** **[**[Previous](#optimize)**]** | | | **[**[Next](#practice)**]**↵

### <strong> <center style="color:red;"> X. Debugging </center> </strong>↵

> Support you when you are in a trouble that you cant find your bug↵

--------------------↵

--------------------↵

##### <span style="color:green;"> A) Wrong answer </span>↵

**1)** Becareful when weight sum and value sum is big, it would cause overflow↵

<spoiler summary="Debug">↵

```cpp↵
long long weight = 0;↵
long long value = 0;↵
```↵

</spoiler>↵

--------------------↵

**2)** Becareful that in Meet-in-the-middle approach: ↵

- You have to update the bitmask that have maxvalue.↵

- You have to update the $maxval$ and $maxmask$ before assign $x.maxval$, $x.maxmask$↵

- You have to use also in collecting the result↵

<spoiler summary="Wrong">↵

```cpp↵
    ll maxval = 0;↵
    for (Node &x : Sr)↵
    {↵
        /// What if x.value > maxval ??↵
        x.maxval = maxval;↵
        x.maxmask = maxmask;↵
        if (maxval < x.value)↵
        {↵
            maxval = x.value;↵
            /// not update maxmask ?↵
        }↵
    }↵
```↵
</spoiler>↵

<spoiler summary="Wrong">↵

```cpp↵
    if (res < x.value + y.value) /// where is maxvalue ?↵
    {↵
        res = x.value + y.value;↵
        mask_l = y.mask;↵
        mask_r = x.mask;↵
    }↵
```↵
</spoiler>↵

<spoiler summary="Wrong">↵

```cpp↵
    if (res < x.maxval + y.value)↵
    {↵
        res = x.maxval + y.value;↵
        mask_l = y.mask;↵
        mask_r = x.mask; /// this mask might not given the maxval !↵
    }↵
```↵
</spoiler>↵

<spoiler summary="Debug">↵

```cpp↵
    ll maxval = 0;↵
    int maxmask = 0;↵
    for (Node &x : Sr)↵
    {↵
        if (maxval < x.value)↵
        {↵
            maxval = x.value;↵
            maxmask = x.mask;↵
        }↵
        x.maxval = maxval;↵
        x.maxmask = maxmask;↵
    }↵
```↵
</spoiler>↵

<spoiler summary="Debug">↵

```cpp↵

    if (res < x.maxval + y.value)↵
    {↵
        res = x.maxval + y.value;↵
        mask_l = y.mask;↵
        mask_r = x.maxmask;↵
    }↵
```↵
</spoiler>↵

--------------------↵

- **3)** Forget base cases: In type $IV$ the DP is already init as 0, so you dont need the loop to zero, while the $V$ is not like that when you init it as $+oo$↵

<spoiler summary="Wrong">↵

```cpp↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    int sum = 0;↵
    for (int i = 1; i <= n; ++i)↵
    {↵
        int c, v;↵
        cin >> c >> v;↵

        sum += v;↵
        for (int s = sum; s >= 1; --s) /// you have to make a loop from s = sum -> 0↵
        {↵
            f[i][s] = f[i - 1][s];↵

            if (s >= v)↵
            {↵
                minimize(f[i][s], f[i - 1][s - v] + c);↵
            }↵
        }↵

        for (int res = sum; res >= 0; --res)↵
        {↵
            if (f[i][res] <= w)↵
            {↵
                cout << res << '\n';↵
                break;↵
            }↵
        }↵
    }↵

</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> B) Time Limit Exceed </span>↵

**1)** Global variable $\neq$ Local variable↵

- In Meet-in-the-middle approach, the `solve()` function **didnt use global variable (n)**, it use $n = |c| = |s|$.↵

<spoiler summary="Debug">↵

```cpp↵
Assign this at the head of the function↵


void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)↵
{↵
    int n = c.size(); /// Important !!!↵
    ...↵
}↵

or↵

void solve(const vector<int> &c, const vector<int> &v, vector<Node> &S)↵
{↵
    int n = v.size(); /// Important !!!↵
    ...↵
}↵

```↵
</spoiler>↵

--------------------↵

**2)** Forget to use memorization↵

<spoiler summary="Wrong">↵

```cpp↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s < 0) return +LINF;↵
    if (i > n) return (s == 0) ? 0 : +LINF;↵

    ll res = f[i][s]; /// is should be &res = [i][s]↵
    if (res != -1) return res;↵
    ll res = +LINF;↵

    minimize(res, magic(i + 1, s - 0) + 0);↵
    minimize(res, magic(i + 1, s - v[i]) + c[i]);↵
    return res;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Wrong">↵

```cpp↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (s < 0) return +LINF;↵
    if (i > n) return (s == 0) ? 0 : +LINF;↵

    ll res = +LINF;↵
    minimize(res, magic(i + 1, s - 0) + 0);↵
    minimize(res, magic(i + 1, s - v[i]) + c[i]);↵
    return f[i][s] = res; /// It is calculated first then assigning dp value↵
}↵
```↵
</spoiler>↵

--------------------↵

**3)** You might get WA if you have wrong initalization or leave the value generated randomly↵

<spoiler summary="Wrong">↵

```cpp↵
    ll f[sum + 1];↵

    /// What if f[x > 0] negative ?↵
    f[0] = 0;↵
    for (int i = 1; i <= n; ++i)↵
        for (int s = sum; s >= v[i]; --s)↵
            minimize(f[s], f[s - v[i]] + c[i]);↵
```↵
</spoiler>↵

--------------------↵

**4)** If you wanna binary search for the result, remember that you cant do Prefixmin DP $O(N \times SUM)$ as what it like in Prefixmax DP $O(N \times W)$↵

<spoiler summary="Wrong">↵

```cpp↵

    ll f[n + 1][sum + 1];↵
    memset(f, +LINF, sizeof(f));↵
    f[0][0] = 0;↵

    for (int i = 1; i <= n; ++i)↵
    {↵
        for (int s = 1; s <= sum; ++s)↵
        {↵
            f[i][s] = min(f[i][s - 1], f[i - 1][s]);↵

            if (s >= v[i])↵
            {↵
                minimize(f[i][s], f[i - 1][s - v[i]] + c[i]);↵
            }↵
        }↵
    }↵

    int res = 0;↵
    for (int l = 1, r = sum; l <= r; )↵
    {↵
        int m = (l + r) >> 1;↵
        if (f[n][m] <= w)↵
        {↵
            res = m;↵
            l = m + 1;↵
        }↵
        else ↵
        {↵
            r = m - 1;↵
        }↵
    }↵
    cout << res;↵
```↵
</spoiler>↵

--------------------↵

--------------------↵

##### <span style="color:green;"> C) Memory limit exceed </span>↵

**1)** Though Meet-in-the-middle approach is faster than Bitmasking Approach, it requires large amount of space &mdash; $O(2^{^{\frac{n}{2}}})$, which may give you MLE !↵

--------------------↵

**2)** In some cases you will need space optimization if the limit is too tight !↵

--------------------↵

**3)** Becareful in tracing results↵

<spoiler summary="Wrong">↵

```cpp↵
    vector<int> selected;↵
    for (int i = n, s = w; i >= 1 && s >= 1; )↵
    {↵
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])↵
        {↵
            selected.push_back(i);↵
            i -= 1;↵
            s -= c[i];↵
        }↵

        if (f[i][s - 1] > f[i - 1][s])↵
        {↵
            --s;↵
        }↵
        else /// f[i][s] = f[i - 1][s]↵
        {↵
            --i;↵
        }↵
    }↵
```↵
</spoiler>↵

<spoiler summary="Fixed">↵

```cpp↵
    vector<int> selected;↵
    for (int i = n, s = w; i >= 1 && s >= 1; )↵
    {↵
        if (f[i][s] == f[i - 1][s - c[i]] + v[i])↵
        {↵
            selected.push_back(i);↵
            s -= c[i]; /// This first then decrease (i)↵
            i -= 1;↵
            continue; /// <--- Important in this case↵
        }↵

        if (f[i][s - 1] > f[i - 1][s])↵
        {↵
            --s;↵
        }↵
        else /// f[i][s] = f[i - 1][s]↵
        {↵
            --i;↵
        }↵
    }↵
```↵
</spoiler>↵


--------------------↵

--------------------↵

##### <span style="color:green;"> D) Runtime Error </span>↵

**1)** Out of bound↵

<spoiler summary="Wrong">↵

```cpp↵
ll f[MAXN][MAXW];↵
ll magic(int i = 1, int s = 0)↵
{↵
    if (i > n) return (s <= w) ? 0 : -LINF;     /// No available item to add into the bag↵

    ll &res = f[i][s]; /// what if (s > w) ?↵
    if (res != -1) return res;↵
        ↵
    maximize(res, magic(i + 1, s + 0) + 0);       /// Not using this item↵
    maximize(res, magic(i + 1, s + c[i]) + v[i]); /// Using this item↵
    return res;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Wrong">↵

```cpp↵
    ll f[n + 1][w + 1];↵
    memset(f, 0, sizeof(f));↵
    for (int i = 1; i <= n; ++i)↵
        for (int s = w; s >= 0; --s)↵
            f[i][s] = max(f[i - 1][s], f[i - 1][s - c[i]] + v[i]); /// What if s < c[i] ?↵
```↵
</spoiler>↵

**2)** Array too big in main function: Declare it globally with the init size bigger than problem constraint a bit↵



























































































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="practice"></a>↵

> **Teleporter:** **[**[Previous](#debug)**]** | | | **[**[Next](#status)**]**↵

### <strong> <center style="color:red;"> XI. Knapsack Variation and Practice Problems </center> </strong>↵

> In case you need a place to practice or submitting↵

--------------------↵

--------------------↵

**1)** [CSES | DP section1158 | Book Shop](https://cses.fi/problemset/task/1158)↵

<spoiler summary="Hint">↵

Type $IV, V$ DP↵
</spoiler>↵

--------------------↵

**2)**[CSES | DP 1634 | Minimizing Coins](https://cses.fi/problemset/task/1634)↵

--------------------↵

- [CSES | DP 1635 | Coin Combinations I](https://cses.fi/problemset/task/1635)↵

--------------------↵

- [CSES | DP 1636 | Coin Combinations II](https://cses.fi/problemset/task/1636)↵

--------------------↵

- [CSES | DP 1745 | Money Sums](https://cses.fi/problemset/task/1745)↵

--------------------↵

- [CSES | DP 1093 | Two Sets II](https://cses.fi/problemset/task/1093)↵

--------------------↵

- [CSES | DP 1665 | Coding Company](https://cses.fi/problemset/task/1665)↵

--------------------↵

-
 [Easy but nice problem](https://training.olinfo.it/#/task/nonna/statement) &mdash; (contributor [user:TheScrasse,2021-03-04])↵

<spoiler summary="Note">↵

The statement is in Italian Language↵

Translated into English: Given an array of length $N$, find the smallest sum $\geq K$ of a subset.↵

Limitation: $N,K \leq 5000 , a_i \leq 10^6$↵

</spoiler>↵


--------------------↵

**3)** [Codeforces #683 Div 11 2020 | Problem 1446A | Knapsack](https://codeforces.me/problemset/problem/1446/A) ↵

<spoiler summary="Hint">↵

Keep adding the items from largest to smallest until they dont fit in the knapsack↵
</spoiler>↵

--------------------↵

**4)** [SPOJ | Classical | Large Knapsack](https://www.spoj.com[Codeforces #360 Div1 2016 | Problem 687C | The Values You Can Make](https://codeforces.me/contest/687/problem/C)↵


--------------------↵

- [Codeforces #522 Div1 2018 | Problem 1078B | The Unbearable Lightness of Weights](https://codeforces.me/contest/1078/problem/B)↵


--------------------↵

- [Codeforces #77 Div1 2011 | Problem 95E | Lucky Country](https://codeforces.me/contest/1078
/problems/LKS//B)↵

--------------------↵

**5)** [SPOJ | Tutorial[Codeforces #26 Edu 2017 | Problem 837D | Round Subset](https://codeforces.me/contest/837/problem/D)↵

--------------------↵

- [Codeforces #61 Edu 2019 | Problem 1132E
 | Knapsack](https://www.spojcodeforces.com/problems/KNAPSACK/et/problem/1132/E)↵

--------------------↵

**6)** [Codeforces #61 Edu | P8VC Venture Cup 2017 | Problem 755F | PolandBall and Gifts](https://codeforces.me/problemset/problem /1132E | Knapsack](https://codeforces.me/problemset/problem/1132/E)↵

--------------------↵

- **7)**
/E)↵

--------------------↵

- [Codeforces Wunder Fund Round 2016 | Double Knapsack](https://codeforces.me/problemset/problem/618/F)↵

--------------------↵

- [Codeforces USP Try-outs 2016 | The Knapsack problem](https://codeforces.me/problemset/problem/618/F)↵

--------------------↵

- [SPOJ | Classical | Large Knapsack](https://www.spoj.com/problems/LKS/)↵

--------------------↵

- [SPOJ | Tutorial | Knapsack](https://www.spoj.com/problems/KNAPSACK/)↵

--------------------↵

-
 [Atcoder DP Contest | Problem D | Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)↵


<spoiler summary="Hint">↵

+ Type $IV$ DP↵
</spoiler>↵

--------------------↵

**8)** [Atcoder DP Contest | Problem E | Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e)↵


<spoiler summary="Hint">↵

+ Type $V$ DP↵
</spoiler>↵

--------------------↵

**9)** [DMOJ | Knapsack 3](https://dmoj.ca/problem/knapsack)↵

--------------------↵

**10)** [DMOJ | Knapsack 4](https://dmoj.ca/problem/knapsack4)↵

--------------------↵

**11)** [Codeforces Wunder Fund Round 2016 | Double Knapsack](https://codeforces.me/problemset/problem/618/F)↵

--------------------↵

- **12)** [
[LQDOJ | Bài toán ba lô 3](https://lqdoj.edu.vn/problem/knapsack3)↵

<spoiler summary="Hint">↵

+ Trace↵

+ Type $III$ DP↵
</spoiler>↵

--------------------↵

**13)** [[LQDOJ | Bài toán ba lô 4](https://lqdoj.edu.vn/problem/knapsack4)↵

<spoiler summary="Hint">↵

+ Trace↵

+ Type $III$ DP &mdash; Meet-in-the-middle Approach↵
</spoiler>↵

--------------------↵

**14)** [[LQDOJ | Bài toán ba lô 5](https://lqdoj.edu.vn/problem/knapsack5)↵

<spoiler summary="Hint">↵

+ Trace↵

+ Type $III$ DP &mdash; Meet-in-the-middle Approach↵
</spoiler>↵


--------------------↵

- [VNOI | Cái túi 1](https://oj.vnoi.info/problem/dttui1)↵

--------------------↵

- [VNOI | Cái túi 2](https://oj.vnoi.info/problem/dttui2)↵

--------------------↵

- [VNOI | Cái túi (Hard version)](https://oj.vnoi.info/problem/hugeknap)↵

--------------------↵

- [VNOI | Bài toán cái túi](https://csp.vnoi.info/problem/knapsack1)↵

--------------------↵

- [VNOI | Túi Fibonacci](https://oj.vnoi.info/problem/qtknap)↵

--------------------↵

- [VNOI | Siêu trộm](https://csp.vnoi.info/problem/knapsack)↵

--------------------↵

- [VNOI | Xếp ba lô](https://csp.vnoi.info/problem/csphn_qhd_knapsack)↵

--------------------↵

- [VNOI | Xếp ba lô 1](https://csp.vnoi.info/problem/csphn_qhd_knapsack1)↵

--------------------↵

- [VNOI | Xếp ba lô knapsack](https://csp.vnoi.info/problem/csphn_qhd_knapsack0)↵

--------------------↵

- [VNOI | Xếp ba lô (nhiều ba lô)](https://csp.vnoi.info/problem/csphn_mknapsack)































































































































































--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵

--------------------↵


| :---: |↵
| ―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――― |↵

<a name="status"></a>↵

> **Teleporter:** **[**[Previous](#practice)**]** | | | **[**[Next](#TOC)**]**↵

### <strong> <center style="color:red;"> XII. Blog status </center> </strong>↵

> The current progress and contributor of this blogs↵

--------------------↵

--------------------↵


- Current progress; 
- Recently

     + **
10)** Online Algorithms↵

     + **2)** Remain space optimization while tracing for element
Added more practice links↵

- On progress:↵

     + **0)** Table of content & Complexity comparision table↵

     + **1)** Online Algorithm↵

     + **2)** Optimizations and Heuristic↵
 ↵
     + **3a)** Unbounded knapsack↵

     + **3b)** Bounded knapsack↵

     + **3c)** Item limitation knapsack↵

     + **4a)** Knapsack query maximum value with item in range $[L, R]$↵

     + **4b)** Knapsack query maximum value with weight in range $[L, R]$↵

     + **4c)** Knapsack query minimum weight with value in range $[L, R]$↵

     + **5a)** Multiple knapsack bags↵

     + **5b)** Multidimentional item↵

     + **6)** Online Algorithms↵

     + **7)** Remain space optimization while tracing for elements↵

     + **8)** Add more problems and ranking them↵

     + **9)** Asking local coordinator for permissions to release private knapsack problems↵

     + **9)** Knapsack 0/1↵
           ↵
- Special thank to contributors: [user:SPyofgame,2021-03-06], [user:TheScrasse,2021-03-06], [user:Lusterdawn,2021-03-06], [user:jiangly,2021-03-06]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SPyofgame 2025-02-03 18:04:40 3302 Added more practice links
en1 English SPyofgame 2021-03-13 20:47:49 106868 Initial revision (published)