Fractional Knapsack Problem ~ Ankur's Blog

Fractional Knapsack Problem

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define MAX 10005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;

	struct Item
	{
	int value, weight;

	Item(int value, int weight) : value(value), weight(weight)
	{}
	};

	bool cmp(struct Item a, struct Item b)
	{
	double r1 = (double) a.value / a.weight;
	double r2 = (double) b.value / b.weight;

	return r1 > r2;
	}

	double fractionalKnapsack(int W, struct Item ar[], int n)
	{
	sort(ar, ar+n, cmp);

	int curWeight = 0;
	double finalValue = 0.0;

	for(int i = 0; i < n; i++){
	if(curWeight+ar[i].weight <= W){
	curWeight += ar[i].weight;
	finalValue += ar[i].value;
	}
	else{
	int remain = W - curWeight;
	finalValue += ar[i].value *( (double) remain/ar[i].weight );
	break;
	}
	}

	return finalValue;
	}


	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/

	int W = 50; // Weight of knapsack
	Item arr[] = {{60, 10}, {100, 20}, {120, 30}};

	int n = sizeof(arr) / sizeof(arr[0]);

	cout << "Maximum value we can obtain = "
	<< fractionalKnapsack(W, arr, n);
	return 0;

	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

	return 0;
	}

Ankur's Blog