Fractional Knapsack Problem

Last updated on July 13th, 2024 at 10:47 am

We will discuss the Fractional Knapsack Problem, pseudo code, Code implementation of Fractional Knapsack in C, Java, JavaScript, Python, advantages & disadvantages, and time complexity of Fractional Knapsack.

1. What is Fractional Knapsack Problem?

The Fractional Knapsack Problem is a classic optimization problem that can be solved using a greedy algorithm.

In the Fractional Knapsack problem, items are given along with their weight and profit. The target is to maximize the profit considering the weight constraint.

Unlike the 0/1 Knapsack problem, you can take fractions of items, meaning you can break the items into smaller pieces.

1.1 Solution by Greedy Algorithm

1. In fractional knapsack, first of all, profit value/weight ratios are calculated and then sorted in descending order.
2. An item with the highest value/weight ratio is chosen and added to the collection.
3. The maximum weight is checked after adding each item.
4. If the entire item cannot be included, then a fraction of it is added to the collection.

2. Pseudocode for Fractional Knapsack

Greedy-fractional-knapsack (w, v, W) 
1. for i =1 to n 
2. Do x[i] =0 
3. weight = 0 
4. while weight < W 
5. Do i = best remaining item
6. if ( weight + w[i] W)
7. Then x[i] = 1 
8. weight = weight + w[i] 
9. else
10. x[i] = (w - weight) / w[i]
11. weight = W
12. Return x

3. Code Implementation of Fractional Knapsack Problem

3.1 Fractional Knapsack in C

#include <stdio.h>

// Structure for an item
struct Item {
    int value;
    int weight;
};

// Comparison function to sort items by value/weight ratio
int compare(const void *a, const void *b) {
    double r1 = (double)((struct Item *)a)->value / ((struct Item *)a)->weight;
    double r2 = (double)((struct Item *)b)->value / ((struct Item *)b)->weight;
    return r2 - r1;
}

// Function to get maximum value
double fractionalKnapsack(int W, struct Item arr[], int n) {
    qsort(arr, n, sizeof(struct Item), compare);
    double totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        } else {
            totalValue += arr[i].value * ((double) W / arr[i].weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    int W = 50;
    struct Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Maximum value we can obtain = %f\n", fractionalKnapsack(W, arr, n));
    return 0;
}

3.1.1 Explanation of Fractional Knapsack

1. Class Item: Defines Item with value and weight.
2. fractional_knapsack Function:
   • Sorts items by value-to-weight ratio.
   • Initializes total_value.
   • Iterates through items, adding them to the knapsack.
3. Example Usage: Initializes W and arr. Calls fractional_knapsack and prints the result.

3.2 Fractional Knapsack in Java

import java.util.Arrays;
import java.util.Comparator;

class Item {
    int value, weight;

    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }
}

public class FractionalKnapsack {
    private static double getMaxValue(int W, Item[] arr) {
        Arrays.sort(arr, new Comparator<Item>() {
            public int compare(Item a, Item b) {
                double r1 = (double) a.value / a.weight;
                double r2 = (double) b.value / b.weight;
                return Double.compare(r2, r1);
            }
        });

        double totalValue = 0.0;

        for (Item item : arr) {
            if (item.weight <= W) {
                W -= item.weight;
                totalValue += item.value;
            } else {
                totalValue += item.value * ((double) W / item.weight);
                break;
            }
        }

        return totalValue;
    }

    public static void main(String[] args) {
        int W = 50;
        Item[] arr = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};

        System.out.println("Maximum value we can obtain = " + getMaxValue(W, arr));
    }
}

3.3 Fractional Knapsack in JavaScript

class Item {
    constructor(value, weight) {
        this.value = value;
        this.weight = weight;
    }
}

function fractionalKnapsack(W, arr) {
    arr.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
    let totalValue = 0;

    for (let item of arr) {
        if (item.weight <= W) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * (W / item.weight);
            break;
        }
    }

    return totalValue;
}

let W = 50;
let arr = [new Item(60, 10), new Item(100, 20), new Item(120, 30)];

console.log("Maximum value we can obtain = " + fractionalKnapsack(W, arr));

3.4 Fractional Knapsack in Python

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

def fractional_knapsack(W, arr):
    arr.sort(key=lambda x: x.value / x.weight, reverse=True)
    total_value = 0

    for item in arr:
        if item.weight <= W:
            W -= item.weight
            total_value += item.value
        else:
            total_value += item.value * (W / item.weight)
            break

    return total_value

W = 50
arr = [Item(60, 10), Item(100, 20), Item(120, 30)]

print("Maximum value we can obtain =", fractional_knapsack(W, arr))

4. Advantages of Fractional Knapsack

1. Efficiency: The greedy approach ensures that we get the optimal solution in a relatively simple and efficient manner.
2. Flexibility: Allows for taking fractions of items, which can be practical in real-world scenarios.

5. Disadvantages of Fractional Knapsack

1. Limited Scope: Only applicable to problems where items can be divided. It doesn’t work for 0/1 Knapsack problems.
2. Sorting Overhead: The need to sort items by their value-to-weight ratio adds to the complexity, making the algorithm O(n log n).

6. Time Complexity of Fractional Knapsack

If the ratio of v_i/w_i is already sorted in decreasing order, then the time taken by the while loop will be O(n). So, the total time required will be O(n log n).

FAQs