0-1 knapsack problem

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

knapsack

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >a;
//dp table is full of zeros
int n,s,dp[1002][1002];
void ini(){
    for(int i=0;i<1002;i++)
        for(int j=0;j<1002;j++)
            dp[i][j]=-1;
}
int f(int x,int b){
	//base solution
	if(x>=n or b<=0)return 0;
	//if we calculate this before, we just return the answer (value diferente of 0)
	if(dp[x][b]!=-1)return dp[x][b];
	//calculate de answer for x (position) and b(empty space in knapsack)
	//we get max between take it or not and element, this gonna calculate all the
	//posible combinations, with dp we won't calculate what is already calculated.
	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);
}
int main(){
	//fast scan and print
	ios_base::sync_with_stdio(0);cin.tie(0);
	//we obtain quantity of elements and size of knapsack
	cin>>n>>s;
	a.resize(n);
	//we get value of elements
	for(int i=0;i<n;i++)
		cin>>a[i].first;
	//we get size of elements
	for(int i=0;i<n;i++)
		cin>>a[i].second;
	//initialize dp table
	ini();
	//print answer
	cout<<f(0,s);
	return 0;
}

Posted by: Guest on May-03-2020

//RECURSSION+MEMOIZATION #include <bits/stdc++.h> using namespace std; int dp[1001][1001]; int knapsack(vector<pair<int,int>>&value,int w,int n) { if(w==0||n==0) { return 0; } if(dp[n][w]!=-1) { return dp[n][w]; } if(value[n-1].first<=w) { return (dp[n][w]=max((value[n-1].second)+knapsack(value,w-(value[n-1].first),n-1),knapsack(value,w,n-1))); } else { return dp[n][w]=knapsack(value,w,n-1); } } int main() { memset(dp,-1,sizeof(dp)); int n; cout<<"ENTER THE NUMBER OF ITEMS: "<<endl; cin>>n; vector<pair<int,int>>value; for(int i=0;i<n;i++) { int a,b; cin>>a>>b; value.push_back(make_pair(a,b));//a->weight and b->price } //sort according to value[i].second in ascending order int w; cout<<"ENTER THE MAX. CAPACITY OF THE KNAPSACK: "; cin>>w; cout<<endl; cout<<knapsack(value,w,n); return 0; }

Code answers related to "0-1 knapsack problem"

Code answers related to "C++"

Browse Popular Code Answers by Language

Answers for "0-1 knapsack problem"

Code answers related to "0-1 knapsack problem"

Code answers related to "C++"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us