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 False
print(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