How to implement an algorithm for the Fractional Knapsack Problem
In this Java tutorial, we are going to implement an algorithm for the fractional knapsack problem.
Knapsack Problem Description
A thief finds a very big loot than his bag size. We have to help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.
Input Format:- The first line of the input contains the number () of items and the capacity (W) of a knapsack.
The next lines define the values and weights of the items. The i-th line contains integers Vi and Wi the value and the weight of the i-th item.
Output Format:- Output the maximum value of fractions of items that fit into his bag.
Step By Step Approach – Knapsack problem in Java
- First, we have to find the value of the item per kg. To find this we have to calculate the value of “Vi/Wi“.
- Now compare the value of each item per kg.
- The item whose value is highest goes first in the bag and compare with the maximum weight bag can take. if the bag is full then it stops here.
- If not then, second highest goes in the bag and compare with the maximum weight bag can take.
- The same process goes on and on until the bag is full.
import java.util.Scanner; public class CodeSpeedy { private static int getMaxIndex(int[] weight, int[] values) { int max_i = 0; double max = 0; for (int i = 0; i < weight.length; i++) { if (weight[i] != 0 && (double) values[i] / weight[i] > max) { max = (double) values[i] / weight[i]; max_i = i; } } return max_i; } private static double getOptimalValue(int capacity_is, int[] values, int[] weight) { double value = 0.0; for (int i = 0; i < weight.length; i++) { if (capacity_is == 0) return value; int index = getMaxIndex(weight, values); int a = Math.min(capacity_is, weight[index]); value += a * (double) values[index] / weight[index]; weight[index] -= a; capacity_is -= a; } return value; } public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int p = scanner.nextInt(); int capacity_is = scanner.nextInt(); int[] values = new int[p]; int[] weight = new int[p]; for (int i = 0; i < p; i++) { values[i] = scanner.nextInt(); weight[i] = scanner.nextInt(); } System.out.println(getOptimalValue(capacity_is, values, weight)); } }
INPUT
3 50 60 20 100 50 120 30
OUTPUT
180.0000
Leave a Reply