knapsack problem

1def greedy_knapsack(values,weights,capacity):
2    n = len(values)
3    def score(i) : return values[i]/weights[i]
4    items = sorted(range(n)  , key=score , reverse = True)
5    sel, value,weight = [],0,0
6    for i in items:
7        if weight +weights[i] <= capacity:
8            sel += [i]
9            weight += weights[i]
10            value += values [i]
11    return sel, value, weight
12
13
14weights = [4,9,10,20,2,1]
15values = [400,1800,3500,4000,1000,200]
16capacity = 20
17
18print(greedy_knapsack(values,weights,capacity))

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}