The Greedy Knapsack Problem/ Fractional Knapsack Problem is a classic example of a greedy algorithm. It differs from the 0/1 Knapsack Problem in that you are allowed to take fractions of an item rather than having to choose to take it or leave it entirely. In this blog post, we’ll walk through a Java implementation of the greedy approach to solving the fractional knapsack problem, explain how the logic works, and break down the sample output.
What is the Greedy Strategy for Knapsack?
In the greedy method, we aim to maximize the total profit by picking items with the highest profit-to-weight ratio. Here’s the approach:
- Calculate the profit-to-weight ratio for each item.
- Sort the items based on this ratio in descending order.
- Select items starting from the highest ratio until the knapsack is full:
- If the item fits, include it completely.
- If not, include as much of it as possible.
Java Code: Greedy Knapsack Implementation
import java.io.*;
class GreedyKnapsack {
public static void knapsack(float m, int n, float w[], float p[]) {
float[] x = new float[n + 1]; // Stores fraction of items included
float profit = 0.0f; // Total profit
float U = m; // Remaining capacity of the knapsack
for (int i = 1; i <= n; i++) x[i] = 0;
for (int i = 1; i <= n; i++) {
if (w[i] > U) break; // If item doesn't fit entirely, break
x[i] = 1.0f; // Take the full item
U -= w[i]; // Decrease capacity
}
// If knapsack is not full and items remain, take fractional part
if (U > 0 && i <= n)
x[i] = U / w[i];
// Calculate total profit
for (int i = 1; i <= n; i++) {
System.out.println("x[" + i + "] = " + x[i]);
profit += p[i] * x[i];
}
System.out.println("\nThe profit earned by the optimal solution is: " + profit);
}
// Sort items by decreasing profit-to-weight ratio
public static void sortObject(int n, float p[], float w[]) {
float[] ratio = new float[n + 1];
for (int i = 1; i <= n; i++) {
ratio[i] = p[i] / w[i];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (ratio[j] < ratio[j + 1]) {
float temp = p[j]; p[j] = p[j + 1]; p[j + 1] = temp;
temp = w[j]; w[j] = w[j + 1]; w[j + 1] = temp;
temp = ratio[j]; ratio[j] = ratio[j + 1]; ratio[j + 1] = temp;
}
}
}
}
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter the number of objects: ");
int n = Integer.parseInt(br.readLine());
System.out.print("Enter the knapsack capacity: ");
float m = Float.parseFloat(br.readLine());
float[] p = new float[n + 1];
float[] w = new float[n + 1];
System.out.println("\nEnter the profit and weight for each object:");
for (int i = 1; i <= n; i++) {
System.out.print("Profit of object " + i + ": ");
p[i] = Float.parseFloat(br.readLine());
System.out.print("Weight of object " + i + ": ");
w[i] = Float.parseFloat(br.readLine());
}
sortObject(n, p, w);
System.out.println("\nThe optimal solution is:");
knapsack(m, n, w, p);
}
}
Sample Output
Enter the number of objects: 3
Enter the knapsack capacity: 20
Enter the profit and weight for each object:
Profit of object 1 : 15
Weight of object 1 : 10
Profit of object 2 : 24
Weight of object 2 : 15
Profit of object 3 : 25
Weight of object 3 : 18
The optimal solution is:
x[1] = 1.0
x[2] = 0.5
x[3] = 0.0
The profit earned by the optimal solution is: 31.5Output Explanation
Let’s understand how the solution was achieved:
- Profit-to-weight ratios:
- Object 1: 15 / 10 = 1.5
- Object 2: 24 / 15 = 1.6
- Object 3: 25 / 18 ≈ 1.39
- Sorted order based on ratios:
- Object 2 (1.6)
- Object 1 (1.5)
- Object 3 (1.39)
- Greedy Selection:
- Take Object 2 fully → weight = 15, profit = 24
- Remaining capacity = 5
- Take part of Object 1 → 5/10 = 0.5 → profit = 15 * 0.5 = 7.5
- Object 3 is skipped
- Total profit = 24 + 7.5 = 31.5
“In life, just like in the knapsack problem, it’s not always about carrying everything — it’s about choosing what brings the most value.”