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.
Item
class: Holds the weight, value, and ratio of each item.getMaxValue
method: Sorts the items by their value-to-weight ratio and then iteratively adds items to the knapsack, considering the capacity constraints.main
method: Creates an array of items, defines the capacity of the knapsack, and calculates the maximum value that can be carried.
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.