Fractional Knapsack is a type of knapsack problem where an algorithm is designed to find the maximum possible value that can be obtained by filling a knapsack of a given capacity with a set of items that have individual weights and values. The key difference between the Fractional Knapsack problem and the 0/1 Knapsack problem is that in the former, the items can be divided into smaller fractions, rather than just being either taken completely or left out.
In Fractional Knapsack, each item has a weight and a value, and the goal is to maximize the total value of items taken, subject to the weight of the knapsack. The algorithm works by calculating a value density for each item, defined as the value of the item divided by its weight. Then, the items are sorted in decreasing order of value density. Starting with the highest value density item, as much of it is added to the knapsack as possible. If it cannot be added in full, then a fraction of it is added to the knapsack. This process continues until the knapsack is full.
The fractional knapsack problem can be solved using the Greedy Algorithm
data class Item(val weight: Double, val value: Double)
fun fractionalKnapsack(items: List<Item>, capacity: Double): Double {
val sortedItems = items.sortedByDescending { it.value / it.weight }
var remainingCapacity = capacity
var totalValue = 0.0
for (item in sortedItems) {
if (remainingCapacity == 0.0) {
break
}
val fraction = minOf(1.0, remainingCapacity / item.weight)
totalValue += fraction * item.value
remainingCapacity -= fraction * item.weight
}
return totalValue
}Item class represents an item with a weight and a value. The fractionalKnapsack function takes a list of items and a capacity and returns the maximum value that can be obtained.
The items are sorted in decreasing order of value density using the sortedByDescending function, which calculates the value density of each item and sorts them accordingly. The function then loops through each item and adds it to the knapsack in fractions as long as there is still capacity left. The amount of the item that can be added to the knapsack is determined by the minOf function, which ensures that the entire item is not added if it exceeds the remaining capacity of the knapsack. The function keeps track of the remaining capacity and the total value of items added to the knapsack.
Finally, the function returns the total value of items added to the knapsack.
data class Item(val weight: Double, val value: Double)
fun fractionalKnapsack(items: List<Item>, capacity: Double): Double {
val sortedItems = items.sortedByDescending { it.value / it.weight }
var remainingCapacity = capacity
var totalValue = 0.0
for (item in sortedItems) {
if (remainingCapacity == 0.0) {
break
}
val fraction = minOf(1.0, remainingCapacity / item.weight)
totalValue += fraction * item.value
remainingCapacity -= fraction * item.weight
}
return totalValue
}
fun main() {
val items = listOf(
Item(10.0, 60.0),
Item(20.0, 100.0),
Item(30.0, 120.0)
)
val capacity = 50.0
val maxValue = fractionalKnapsack(items, capacity)
println("The maximum value that can be obtained is $maxValue")
}In this example, we have a list of three items with their respective weights and values, and a knapsack with a capacity of 50. We call the getMaximumValue function to obtain the maximum value that can be obtained using fractional knapsack algorithm and print the result to the console.
Output : The maximum value that can be obtained is 240.0