Java Program to Solve the Fractional Knapsack Problem
The Fractional Knapsack Problem is a classic optimization problem that falls under the category of greedy algorithms. Given a set of items, each with a weight and a value, the goal is to determine the maximum value that can be carried in a knapsack of a given capacity, where items can be divided into smaller parts.
What is the Fractional Knapsack Problem?
In the Fractional Knapsack Problem, unlike the 0/1 Knapsack Problem, you can take fractions of items. This allows you to achieve the optimal solution by considering the value-to-weight ratio of each item and taking as much as possible of the item with the highest ratio.
Greedy Approach to Solve the Problem
The greedy approach to solving the Fractional Knapsack Problem involves the following steps:
- Calculate the value-to-weight ratio for each item.
- Sort the items based on the value-to-weight ratio in descending order.
- Iterate through the sorted list and add as much of each item as possible to the knapsack until the knapsack is full.
Java Program to Implement Fractional Knapsack Problem
Below is the implementation of the Fractional Knapsack Problem:
// Java Program to Implement Fractional Knapsack Problem
import java.util.Arrays;
import java.util.Comparator;
// Class representing an item with weight,
// value, and value-to-weight ratio
class Item {
double weight, value, ratio;
// Constructor to initialize an item with weight
// and value, and calculate the ratio
Item(double weight, double value) {
this.weight = weight;
this.value = value;
this.ratio = value / weight;
}
}
public class FractionalKnapsack {
// Method to calculate the maximum value
// that can be carried in the knapsack
public static double getMaxValue(Item[] items, double capacity) {
// Sort items by their value-to-weight
// ratio in descending order
Arrays.sort(items, new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return Double.compare(o2.ratio, o1.ratio);
}
});
// Variable to keep track of the total
// value in the knapsack
double totalValue = 0;
// Iterate through the sorted items
for (Item item : items) {
if (capacity - item.weight >= 0) {
// If the item can be completely
// added to the knapsack
capacity -= item.weight;
totalValue += item.value;
} else {
// If only part of the item can be
// added to the knapsack
totalValue += item.value * (capacity / item.weight);
// No more capacity left, exit the loop
break;
}
}
// Return the total value accumulated
return totalValue;
}
// Main method
public static void main(String[] args) {
// Array of items with specified weights and values
Item[] items = {
new Item(10, 60),
new Item(20, 100),
new Item(30, 120)
};
// Knapsack capacity
double capacity = 50;
// Calculate the maximum value that can
// be carried and print the result
double maxValue = getMaxValue(items, capacity);
System.out.println("Maximum value in knapsack: " + maxValue);
}
}
Output
Maximum value in knapsack: 240.0
Explanation of the Code:
The code defines a class Item with attributes for weight, value, and value-to-weight ratio. The main class FractionalKnapsack contains the getMaxValue method, which implements the greedy algorithm.
Itemclass: Holds the weight, value, and ratio of each item.getMaxValuemethod: Sorts the items by their value-to-weight ratio and then iteratively adds items to the knapsack, considering the capacity constraints.mainmethod: Creates an array of items, defines the capacity of the knapsack, and calculates the maximum value that can be carried.
Conclusion
The Fractional Knapsack Problem is effectively solved using a greedy approach. By prioritizing items with the highest value-to-weight ratio, we can achieve the maximum possible value within the given capacity. This method is efficient and guarantees an optimal solution.
Frequently Asked Questions
1. What is the time complexity of the greedy algorithm for the Fractional Knapsack Problem?
The time complexity is O(n log n) due to the sorting step, where n is the number of items.
2. Can the Fractional Knapsack Problem be solved using Dynamic Programming?
No, dynamic programming is used for the 0/1 Knapsack Problem. The Fractional Knapsack Problem is optimally solved using a greedy approach.
3. What happens if two items have the same value-to-weight ratio?
If two items have the same ratio, their order in the sorted list does not affect the final solution, as the algorithm will add them both based on the available capacity.