--

# 0–1 knapsack

Given an array a, which may contain negative value. Check whether this array contains a subsequence whose sum is equal to a target

`# Online Python compiler (interpreter) to run Python online.# Write Python 3 code in this online editor and run it.def check_target(a, target):    hist = {0}    for item in a:        for old_target_sum in list(hist):            if item + old_target_sum == target:return True            hist.add(item+old_target_sum)    return Falseprint(print(check_target([1,2,3,4,5,6], 7)))`

A nice video about using multiset in C++ can be found HERE.

`#include <iostream>#include <vector>#include<bits/stdc++.h> //int dp[100][10000];using namespace std;int get_ret(vector<vector<int>> &water, int m){    const int n = water.size();    vector<int> dp(m+1, INT_MAX);    dp[0] = 0;    int ret = INT_MAX;    for(int i=0;i<n;++i)    {        vector<int> new_dp(m+1, INT_MAX);        auto w=water[i][0], c = water[i][1];        for(int j=0;j<=m;j++)        {            if(dp[j]!=INT_MAX)            {                auto new_pos = j;                auto num = 0;                while(true)                {                    new_dp[new_pos] = min(new_dp[new_pos], dp[j]+num*c);                    new_pos += w;                    num ++;                    if(new_pos==m)                    {                        new_dp[new_pos] = min(new_dp[new_pos], dp[j]+num*c);                        dp = new_dp;                        ret = min(ret, new_dp[m]);                        break;                    }                    else if(new_pos>m)                    {                        dp = new_dp;                        ret = min(ret, dp[j]+num*c);                        break;                    }                }            }        }            }    return ret;}int main(){    int n;    cin >> n;    for(int i=0;i<n;++i)    {        //memset(dp, 0, sizeof(dp));        vector<vector<int>> water;        int row, m;        cin >> row >> m;        for(int j=0;j<row;++j)        {            int a, b;            cin >> a >> b;            water.push_back(vector<int>{a, b});        }        auto ret = get_ret(water, m);        cout<<ret<<endl;    }    return 0;}`

Improved version

`#include <iostream>#include <vector>#include<bits/stdc++.h> //int dp[100][10000];using namespace std;int get_ret(vector<vector<int>> &water, int m){    const int n = water.size();    vector<int> dp(m+1, INT_MAX);    dp[0] = 0;    int ret = INT_MAX;    for(int i=0;i<n;++i)    {        auto w=water[i][0], c = water[i][1];        for(int j=0;j<=m+w-1;++j)        {            if(j-w>=0 && j<=m &&dp[j-w]!=INT_MAX)dp[j] = min(dp[j], dp[j-w]+c);            if(j-w>=0 && j>m  && dp[j-w]!=INT_MAX)dp[m] = min(dp[m], dp[j-w]+c);        }        //dp = new_dp;    }    return dp[m];}int main(){    int n;    cin >> n;    for(int i=0;i<n;++i)    {        //memset(dp, 0, sizeof(dp));        vector<vector<int>> water;        int row, m;        cin >> row >> m;        for(int j=0;j<row;++j)        {            int a, b;            cin >> a >> b;            water.push_back(vector<int>{a, b});        }        auto ret = get_ret(water, m);        cout<<ret<<endl;    }    return 0;}`

# Complete knapsack

## Binarysearch: Making Change Sequel

Naively do it we will get TLE as the time complexity is O(N*W²)

Actually, each time we can add the value of n based on the smaller index location, then it will be accumulated updated. For example:

we begin from 0,

0 + 2 -> 2

when move to 2, 2 + 2 -> 4

when move to 4, 4 + 2 →6

If means we stand from 0, we can achieve 0 + 1*2, 0 + 2*2, 0 + 3*2 …

TLE version

`const int AMOUNT =5e5+10;const int N = 11;const int INF = 0x3f3f3f3f;int memo[N][AMOUNT];int solve(vector<int>& denominations_, int amount) {    memset(memo, 0x3f, sizeof memo);vector<int> denominations;for (auto d: denominations_)if(d)denominations.push_back(d);    const int n = denominations.size();int ret = INT_MAX;    for (int i = 0; i < n; ++i){        int d = denominations[i];       // if (d == 0) continue;        if (i == 0){            for (int j = 0; j <= amount / d; ++j){                int new_amt = j*d;                                memo[0][j*d] = j;                if (new_amt == amount) ret = min(ret, memo[0][j*d]);            }            continue;        }         for (int amt = 0; amt <= amount; ++amt){            if (memo[i-1][amt] != INF){                for (int j = 0; amt + d*j <= amount; ++j){                    int new_amt = amt + j*d;                    memo[i][new_amt] = min(memo[i][new_amt] , memo[i-1][amt] + j);                     if (new_amt == amount) ret = min(ret, memo[i][amount]);                }            }        }           }     return ret == INT_MAX? -1: ret;}`

Non TLE version

`int solve(vector<int>& denominations, int amount) {    vector<int> memo(amount + 1, INT_MAX);    memo[0] = 0;    for (auto &d: denominations){        if (d == 0) continue;        for (int amt = 0; amt <= amount; ++amt){            if(amt + d <= amount && memo[amt] != INT_MAX)memo[amt + d] = min(memo[amt + d], memo[amt] + 1);        }    }    return memo[amount] ==INT_MAX? -1:  memo[amount]; }`

--

--