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

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

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Beginner’s guide to Data Science — Python + Docker

Deploying an AWS Lambda Function that Processes Historical Data from a Dynamo DB Table and Uploads…

My Recursion Comic

[Vulnhub] Kioptrix 3 (1.2) Write-up

SyncroB.it Has Arrived!

5 Useful Tricks To Rewrite Your Git History

list of Git messages

Good to Great — How to become a top 5% developer in 2021!

Reveal the face of live video Streaming and blur the face Using OpenCV

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

ML Models on Petabytes of Data — You Need GPUs

Feature scaling

How can engineering interns contribute to a data science team?

Students in class coding on their computers