Fractional Knapsack Implementation in Java

This code snippet demonstrates the implementation of the fractional knapsack problem using Java. Items are sorted based on their value-to-weight ratio, and the maximum profit is calculated considering fractional parts of items that can fit into the knapsack's capacity.
 avatar
unknown
java
a year ago
1.5 kB
11
Indexable
import java.util.*;

class Item {

    int weight;
    int value ;

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

}

public class Solution {
   public static double fractionalKnapsackHelper(Item items[], int capacity) {

        Arrays.sort(items, (o1, o2) -> {

            double ratio1 = (double) o1.value / o1.weight;
            double ratio2 = (double) o2.value / o2.weight;

            if (ratio1 > ratio2)
                return -1;
            if (ratio1 < ratio2)
                return 1;

            return 0;
        });

        double profit = 0;

        for (int i = 0; i < items.length; i++) {

            if (items[i].weight <= capacity) {

                profit += items[i].value;
                capacity -= items[i].weight;
            } else {

                double fracProf = (double) (capacity * items[i].value) / items[i].weight;
                profit += fracProf;

                break;
            }
        }

        return profit;

    }

    public static double fractionalKnapsack(int[] values, int[] weights, int capacity) {
        // You can code here

        Item[] items = new Item[values.length];

        for (int i = 0; i < values.length; i++) {

            items[i] = new Item(values[i], weights[i]);
        }

        return fractionalKnapsackHelper(items, capacity);

    }
}
Editor is loading...
Leave a Comment