knapsackFructional.cpp

#include<bits/stdc++.h>
using namespace std;
void k(int n,int cap,int *weight,int *profit,float *rat)
{
    
    float tp=0,rc=cap;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(rat[i]<rat[j])
            {
                swap(rat[j],rat[i]);
                swap(weight[j],weight[i]);
                swap(profit[j],profit[i]);
            }
        }
    }
    int i;

    for(i=0; i<n; i++)
    {
        if(weight[i]>rc) 
        {
             tp+=(rc/weight[i])*profit[i];
             break;
        }
        else
        {
            tp+=profit[i];
            rc-=weight[i];
        }
    }
    
    
    cout<<tp;

}
int main()
{

    int n,capacity;
    cin>>n>>capacity;
    int weight[n],profit[n];
    float rat[n];
    for(int i=0; i<n; i++)  cin>>weight[i];
    for(int i=0; i<n; i++) cin>>profit[i];

    for(int i=0; i<n; i++) rat[i]=profit[i]*1.0/weight[i];
    for(int i=0;i<n;i++) cout<<rat[i]<<" ";
    cout<<endl;
    k(n,capacity,weight,profit,rat);
}



/* 

#include <bits/stdc++.h>
using namespace std;

struct Item{
    int value;
    int weight;
};

 bool cmp(Item a, Item b)
    {
        return a.value/(a.weight*1.0)>b.value/(b.weight*1.0);
    }


    //Function to get the maximum total value in the knapsack.
    double fractionalKnapsack(int W, Item arr[], int n)
    {
        // Your code here
        sort(arr,arr+n,cmp);
        double res=0.00;
        for(int i=0;i<n;i++){
            auto x=arr[i];
            if(x.weight<=W){
                W-=x.weight;
                res+=x.value;
            }
            else{
                res+=W*x.value/(1.0*x.weight);
                break;
            }
        }
        return res;
    }



int main()
{
	int n,w;
	cin>>n>>w;

		Item arr[n];
		//value and weight of each item
		for(int i=0;i<n;i++){
			cin>>arr[i].value>>arr[i].weight;
		}

		cout<<fractionalKnapsack(w,arr, n)<<endl;
	}


 */