fractional knapsack problem

def greedy_knapsack(values,weights,capacity): n = len(values) def score(i) : return values[i]/weights[i] items = sorted(range(n) , key=score , reverse = True) sel, value,weight = [],0,0 for i in items: if weight +weights[i] <= capacity: sel += [i] weight += weights[i] value += values [i] return sel, value, weight weights = [4,9,10,20,2,1] values = [400,1800,3500,4000,1000,200] capacity = 20 print(greedy_knapsack(values,weights,capacity))

/*Given Weights and values of n items, we need to put these items in a knapsack
  of capacity W to get the maximunm value in the knapsack.
  Sample Input:N=3
  			   W=50;arr[]={{60,10},{100,20},{120,30}};
  Sample Output:240
  TC=O(nlogn)
*/
#include<bits/stdc++.h>
using namespace std;
struct item
{
    int value,weight;
};
bool cmp(item a,item b)
{
    double r1=(double)a.value/a.weight;
    double r2=(double)b.value/b.weight;
    return(r1>r2);
}
double fractionalknapsack(item arr[],int w,int n)
{
    sort(arr,arr+n,cmp);
    int cur_weight=0;
    double final_val=0.0;
    for(int i=0;i<n;i++)
    {
        if(cur_weight+arr[i].weight<=w)
        {
            cur_weight+=arr[i].weight;
            final_val+=arr[i].value;
        }
        else
        {
            int remain=w-cur_weight;
            final_val+=arr[i].value*((double)remain/arr[i].weight);
        }
    }
    return final_val;
}
int main()
{
    int n;
    cout<<"Enter the number of items:"<<endl;
    cin>>n;
    int w;
    cout<<"enter the maximum weight:"<<endl;
    cin>>w;
    item arr[n];
    cout<<"enter the value and weights:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i].value>>arr[i].weight;
    }
    double ans=fractionalknapsack(arr,w,n);
    cout<<ans;
    return 0;
}

Posted by: Guest on July-17-2021

#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; }

Code answers related to "fractional knapsack problem"

Code answers related to "C++"

Browse Popular Code Answers by Language

Answers for "fractional knapsack problem"

Code answers related to "fractional knapsack problem"

Code answers related to "C++"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us