FractionalKnapsack

package algorithms;

import java.util.Arrays;
import java.util.Comparator;

public class FractionalKnapsack {

    static class Item {
	int value, weight;

	public Item(int value, int weight) {
	    this.value = value;
	    this.weight = weight;
	}
    }

    // Main greedy function to solve problem
    static double fractionalKnapsack(int W, Item[] arr, int n) {
	// sorting Item on basis of val/wt ratio
	Arrays.sort(arr, new Comparator<Item>() {
	    @Override
	    // note how using o2 first gives a desc comparator which is not
	    // default
	    public int compare(Item o1, Item o2) {
	      return (int) ((o2.value / o2.weight) - (o1.value / o1.weight));
	    }
	});

	for (int i = 0; i < n; i++) {
	    System.out.println(arr[i].value + "  " + arr[i].weight);
	}

	int curWeight = 0; // current weight in knapsack
	double finalvalue = 0.0; // result (value in knapsack)

	// Looping through all Items take greedily
	for (int i = 0; i < n; i++) {
	    // If adding Item won't overflow, add it completely
	    if (curWeight + arr[i].weight <= W) {
		curWeight += arr[i].weight;
		finalvalue += arr[i].value;
		// If we can't add current Item, add fractional part of it
	    } else {
		int remain = W - curWeight;
		finalvalue += arr[i].value * ((double) remain / arr[i].weight);
		break;
	    }
	}
	// Returning final value
	return finalvalue;
    }
    public static void main(String[] args) {
	Item[] arr = { new Item(100, 20), new Item(60, 10), new Item(120, 30) };
	System.out.println(fractionalKnapsack(50, arr, arr.length));
    }
}