# 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 **V i** and

**W**the value and the weight of the i-th item.

*i***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 “V
*i*/W*i*“. - 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

You must be logged in to post a comment.