knapsack problem

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 False
print(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]; 
}

Reference

[1]https://www.bilibili.com/video/BV1sb411r7UM?p=2

[2]https://v.douyu.com/show/l0Q8mMY0N9N749Ad?ap=1