0 1 knapsack problem

1#Returns the maximum value that can be stored by the bag
2
3def knapSack(W, wt, val, n):
4   # initial conditions
5   if n == 0 or W == 0 :
6      return 0
7   # If weight is higher than capacity then it is not included
8   if (wt[n-1] > W):
9      return knapSack(W, wt, val, n-1)
10   # return either nth item being included or not
11   else:
12      return max(val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
13         knapSack(W, wt, val, n-1))
14# To test above function
15val = [50,100,150,200]
16wt = [8,16,32,40]
17W = 64
18n = len(val)
19print (knapSack(W, wt, val, n))

1//RECURSSION+MEMOIZATION
2#include <bits/stdc++.h>
3using namespace std;
4int dp[1001][1001];
5int knapsack(vector<pair<int,int>>&value,int w,int n)
6{
7    if(w==0||n==0)
8    {
9        return 0;
10    }
11    if(dp[n][w]!=-1)
12    {
13        return dp[n][w];
14    }
15        if(value[n-1].first<=w)
16        {
17
18            return (dp[n][w]=max((value[n-1].second)+knapsack(value,w-(value[n-1].first),n-1),knapsack(value,w,n-1)));
19        }
20        else
21        {
22            return dp[n][w]=knapsack(value,w,n-1);
23        }
24}
25int main()
26{
27    memset(dp,-1,sizeof(dp));
28    int n;
29    cout<<"ENTER THE  NUMBER OF ITEMS: "<<endl;
30    cin>>n;
31    vector<pair<int,int>>value;
32    for(int i=0;i<n;i++)
33    {
34        int a,b;
35        cin>>a>>b;
36        value.push_back(make_pair(a,b));//a->weight and b->price
37    }
38    //sort according to value[i].second in ascending order 
39    int w;
40    cout<<"ENTER THE MAX. CAPACITY OF THE KNAPSACK: ";
41    cin>>w;
42    cout<<endl;
43    cout<<knapsack(value,w,n);
44
45    return 0;
46}
47

1#include<bits/stdc++.h>
2using namespace std;
3vector<pair<int,int> >a;
4//dp table is full of zeros
5int n,s,dp[1002][1002];
6void ini(){
7    for(int i=0;i<1002;i++)
8        for(int j=0;j<1002;j++)
9            dp[i][j]=-1;
10}
11int f(int x,int b){
12	//base solution
13	if(x>=n or b<=0)return 0;
14	//if we calculate this before, we just return the answer (value diferente of 0)
15	if(dp[x][b]!=-1)return dp[x][b];
16	//calculate de answer for x (position) and b(empty space in knapsack)
17	//we get max between take it or not and element, this gonna calculate all the
18	//posible combinations, with dp we won't calculate what is already calculated.
19	return dp[x][b]=max(f(x+1,b),b-a[x].second>=0?f(x+1,b-a[x].second)+a[x].first:INT_MIN);
20}
21int main(){
22	//fast scan and print
23	ios_base::sync_with_stdio(0);cin.tie(0);
24	//we obtain quantity of elements and size of knapsack
25	cin>>n>>s;
26	a.resize(n);
27	//we get value of elements
28	for(int i=0;i<n;i++)
29		cin>>a[i].first;
30	//we get size of elements
31	for(int i=0;i<n;i++)
32		cin>>a[i].second;
33	//initialize dp table
34	ini();
35	//print answer
36	cout<<f(0,s);
37	return 0;
38}
39