What is the Fractional Knapsack Problem?

The Fractional Knapsack Problem is a classic optimization problem in computer science and mathematics. It is a variation of the Knapsack Problem, which involves selecting items with specific weights and values to maximize the value within a limited capacity. In the Fractional Knapsack Problem, we can take fractions of items to enable a more flexible approach. In this Answer, we will explore the Fractional Knapsack Problem, understand its principles, see how it can be solved, and examine its applications.

Before diving into this Answer, it is helpful to have an overview of the Knapsack Problem

Fractional Knapsack Problem

The Fractional Knapsack Problem is a combinatorial optimization problem that can be defined as described below.

Problem statement

Given a set of items, each with a weight w and a value v, and a knapsack with a maximum weight capacity W, we have to select a combination of items to maximize the total value of the items in the knapsack while not exceeding the weight capacity.

Unlike the classic Knapsack Problem, in the Fractional Knapsack Problem, we can take fractions of items. This added flexibility makes it suitable when items can be divided into smaller portions, such as loading trucks with fractional weights or cutting materials into pieces.

Steps to calculate

The Fractional Knapsack Problem can be solved using a greedy algorithm. The algorithm follows these steps:

Calculating the value-to-weight ratio (value/weight) for each item
Sorting the items in descending order of their value-to-weight ratio
Initializing the knapsack as empty and setting the total value to $0$
Adding items to the knapsack until the weight capacity is reached, starting with the item with the highest value-to-weight ratio
If space is left in the knapsack, adding a fraction of the next item that maximizes the value

Illustrating an example

Let’s illustrate the Fractional Knapsack Problem with an example:

def fractional_knapsack(items, capacity):
    items.sort(key=lambda item: item[1] / item[0], reverse=True)
    
    selected_items = []
    value = 0
    for item in items:
        weight, value = item
        if capacity >= weight:
            selected_items.append((weight, value))
            value += value
            capacity -= weight
        else:
            fraction = capacity / weight
            selected_items.append((capacity, fraction * value))
            value += fraction * value
            break
    return selected_items, value
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
result, max_value = fractional_knapsack(items, capacity)
print("Selected items:", result)
print("Total value:", max_value)

Code explanation

Line 2: We sort the items list in descending order based on the value-to-weight ratio of each item. It calculates this ratio for each item by dividing its value (index 1) by its weight (index 0) and then sorts the items accordingly.
Lines 4–5: Here, we initialize an empty list called selected_item and a variable named value to 0. The value variable keeps track of the total value of the items selected for the knapsack, whereas the list stores the items selected for the knapsack.
Lines 7–8: We start a for loop that iterates through each item in the items list. Each item is represented as a tuple containing its weight and value. The item tuple is unpacked into two variables: weight and value.
Lines 9–12: We check for enough capacity in the knapsack to hold the entire item. If so, it adds the entire item (weight and value) to selected_items, increments the value, and updates the remaining knapsack capacity.
Lines 13–17: In cases of insufficient capacity, we calculate the fraction of the current item that can be added, add it to selected_items along with the remaining capacity and the fractional value increments the total value, and exit the loop because the knapsack is full.
Line 19: We return the selected_items and the value, representing the total value of the items in the knapsack.
Lines 23–25: We initialize a list of tuples named items to represent items as tuples with weight (in kilograms) and value (in dollars). The capacity variable is set to 50, indicating the knapsack’s maximum weight limit. We apply the fractional_knapsack function to select items for maximum value within the capacity. It returns result and max_value.
Lines 26–27: We print the selected items and fractions from result and max_value, representing the maximum attainable total value.

Conclusion

The Fractional Knapsack Problem is a versatile optimization problem with practical applications in various fields. Understanding the problem’s principles and how to solve it using the greedy algorithm is valuable for decision-making in resource allocation and optimization scenarios. Illustrations and interactive demonstrations can enhance comprehension and application of this problem-solving technique.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

You TubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources