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# a dynamic approach
2# Returns the maximum value that can be stored by the bag
3def knapSack(W, wt, val, n):
4 K = [[0 for x in range(W + 1)] for x in range(n + 1)]
5 #Table in bottom up manner
6 for i in range(n + 1):
7 for w in range(W + 1):
8 if i == 0 or w == 0:
9 K[i][w] = 0
10 elif wt[i-1] <= w:
11 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
12 else:
13 K[i][w] = K[i-1][w]
14 return K[n][W]
15#Main
16val = [50,100,150,200]
17wt = [8,16,32,40]
18W = 64
19n = len(val)
20print(knapSack(W, wt, val, n))
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
1'''
2Capacity of knapsack = W
3weight list : wt = []
4price list : pr = []
5No. of items = N
6'''
7def kProfit(W,N,wt,pr,dp):
8 # Base Condition
9 if N==0 or W==0:
10 return 0
11 # If sub problem is previously solved tehn return it.
12 if dp[N][W] is not None:
13 return dp[N][W]
14 if wt[N-1] <= W:
15 dp[N][W] = max(pr[N-1]+kProfit(W-wt[N-1],N-1,wt,pr,dp), kProfit(W,N-1,wt,pr,dp))
16 return dp[N][W]
17 else:
18 dp[N][W] = kProfit(W,N-1,wt,pr,dp)
19 return dp[N][W]
20if __name__ == '__main__':
21 W = 11
22 wt = [1, 2, 5, 6, 7]
23 pr = [1, 6, 18, 22, 28]
24 N = len(pr)
25 # define DP array
26 dp = [[None] * (W + 1) for _ in range(N + 1)]
27 # Call for kProfit to calculate max profit
28 maxProfit = kProfit(W,N,wt,pr,dp)
29 print('Maximum Profit is : ',maxProfit)
30
1// memory efficient and iterative approach to the knapsack problem
2
3#include <bits/stdc++.h>
4using namespace std;
5
6// n is the number of items
7// w is the knapsack's capacity
8int n, w;
9
10int main() {
11/*
12input format:
13n w
14value_1 cost_1
15value_2 cost_2
16.
17.
18value_n cost_n
19*/
20 cin >> n >> w;
21 vector<long long> dp(w + 1, 0);
22
23 for (int i = 0; i < n; ++i) {
24 int value, cost;
25 cin >> value >> cost;
26 for (int j = w; j >= cost; --j)
27 dp[j] = max(dp[j], value + dp[j - cost]);
28 }
29
30 // the answer is dp[w]
31 cout << dp[w];
32}