> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/greedy/fractional-knapsack-problem.md).

# Fractional Knapsack Problem

Given weights and values of n items, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

In the [0-1 Knapsack problem](https://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/), we are not allowed to break items. We either take the whole item or don’t take it.

> Input:\
> Items as (value, weight) pairs\
> arr\[] = {{60, 10}, {100, 20}, {120, 30}}\
> Knapsack Capacity, W = 50;\
> Output:\
> Maximum possible value = 240\
> by taking items of weight 10 and 20 kg and 2/3 fraction\
> of 30 kg. Hence total price will be 60+100+(2/3)(120) = 240

```java
public class Main {
    static class ItemValue {
        double wt, val;
        Double cost;
        public ItemValue(int wt, int val) {
            this.wt = wt;
            this.val = val;
            cost = new Double(val / wt);
        }
    }

    public static double getMaxValue(int[] wt, int[] val, int capacity) {
        ItemValue[] iVal = new ItemValue[wt.length];
        for (int i = 0; i < wt.length; i++) {
            iVal[i] = new ItemValue(wt[i], val[i]);
        }
        Arrays.sort(iVal, (a, b) -> b.cost.compareTo(a.cost));
        double totalValue = 0d;
        for (ItemValue i : iVal) {
            int curWt = (int) i.wt;
            int curVal = (int) i.val;
            if (capacity - curWt >= 0) {
                // item can be picked whole
                capacity = capacity - curWt;
                totalValue += curVal;
            } else {
                // item cant be picked whole
                double fraction = ((double) capacity / (double) curWt);
                totalValue += (curVal * fraction);
                capacity = (int) (capacity - (curWt * fraction));
                break;
            }
        }
        return totalValue;
    }
}
```