1. Introduction

The fractional knapsack problem is a variation of the classical 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. However, unlike the classical knapsack problem, we are allowed to break items. The greedy approach suggests that we pick items in decreasing order of value per unit weight.

2. Program Steps

1. Compute the ratio (value/weight) for each item.

2. Sort items based on the computed ratio in decreasing order.

3. Add items to the knapsack based on the decreasing ratio until the capacity is filled.

3. Code Program

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

class Item {
    int value, weight;
    Item(int x, int y) {
        this.value = x;
        this.weight = y;
    }
}

public class FractionalKnapSack {

    static double fractionalKnapSack(int W, Item arr[], int n) {
        Arrays.sort(arr, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o2.value * o1.weight - o1.value * o2.weight;
            }
        });

        int curWeight = 0;
        double finalvalue = 0.0;

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

        return finalvalue;
    }

    public static void main(String[] args) {
        int W = 50;
        Item[] arr = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
        int n = arr.length;

        System.out.println("Maximum value obtained = " + fractionalKnapSack(W, arr, n));
    }
}

Output:

Maximum value obtained = 240.0

4. Step By Step Explanation

1. Item: This class is used to define an item with value and weight.

2. fractionalKnapSack: This is the main function where the logic of the greedy algorithm for the knapsack problem is implemented. It returns the maximum value that can be obtained.

3. The main function initializes the knapsack weight W, the items (with their values and weights), and then calls fractionalKnapSack.