# 0–1 knapsack

`# 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)))`
`#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;}`
`#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;}`

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi