Computer scienceProgramming languagesJavaInterview preparationAlgorithms and problem solving techniques

Greedy algorithms

Theory

Fractional knapsack problem

Report a typo

You are given the solution to the fractional knapsack problem. Unfortunately, the previous developer forgot to complete the part when you put an item in the knapsack. Your task is to finish the missing block of code.

[ALERT-primary]

To imitate the human approach, just imagine physically putting an item in the bag. How would the total value and the remaining capacity of the bag change after this action?

[/ALERT-primary]

Sample Input 1: 

10, 15, 30
60, 80, 120
50

Sample Output 1: 

Maximum Knapsack capacity: 50
Maximum value of given items: 240.0
Write a program in Java 17
import java.util.*;

class KnapsackProblem {
public static double getMaxKnapsackValue(int[] weights, int[] values, int capacity) {
int itemNumber = weights.length;
Item[] items = new Item[itemNumber];

// 1. Create an array of items with weight and value pairs
for (int i = 0; i < itemNumber; i++) {
items[i] = new Item(weights[i], values[i]);
}

// 2. Sort items based on the value per weight ratio
Comparator<Item> comparator = Comparator.comparingDouble(Item::getRatio).reversed();
Arrays.sort(items, comparator);

double totalValue = 0.0;
int remainingCapacity = capacity;

// 3. Fill the knapsack with items
for (Item item : items) {
if (remainingCapacity >= item.weight) {
// 3.1 Put the whole item
// !!! DO NOT CHANGE THE CODE ABOVE !!!

totalValue = ???
remainingCapacity = ???

// !!! DO NOT CHANGE THE CODE BELOW !!!
} else {
// 3.2 Take a fraction possible capacity of the item and put it
// Break the cycle when put last fractional item
double fractionCapacity = (double) remainingCapacity / item.weight;
totalValue += fractionCapacity * item.value;
break;
}
___

Create a free account to access the full topic