fractional 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/*Given Weights and values of n items, we need to put these items in a knapsack
2  of capacity W to get the maximunm value in the knapsack.
3  Sample Input:N=3
4  			   W=50;arr[]={{60,10},{100,20},{120,30}};
5  Sample Output:240
6  TC=O(nlogn)
7*/
8#include<bits/stdc++.h>
9using namespace std;
10struct item
11{
12    int value,weight;
13};
14bool cmp(item a,item b)
15{
16    double r1=(double)a.value/a.weight;
17    double r2=(double)b.value/b.weight;
18    return(r1>r2);
19}
20double fractionalknapsack(item arr[],int w,int n)
21{
22    sort(arr,arr+n,cmp);
23    int cur_weight=0;
24    double final_val=0.0;
25    for(int i=0;i<n;i++)
26    {
27        if(cur_weight+arr[i].weight<=w)
28        {
29            cur_weight+=arr[i].weight;
30            final_val+=arr[i].value;
31        }
32        else
33        {
34            int remain=w-cur_weight;
35            final_val+=arr[i].value*((double)remain/arr[i].weight);
36        }
37    }
38    return final_val;
39}
40int main()
41{
42    int n;
43    cout<<"Enter the number of items:"<<endl;
44    cin>>n;
45    int w;
46    cout<<"enter the maximum weight:"<<endl;
47    cin>>w;
48    item arr[n];
49    cout<<"enter the value and weights:"<<endl;
50    for(int i=0;i<n;i++)
51    {
52        cin>>arr[i].value>>arr[i].weight;
53    }
54    double ans=fractionalknapsack(arr,w,n);
55    cout<<ans;
56    return 0;
57}
58

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