Fractional Knapsack Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Fractional Knapsack Problem?

To maximize the total value of items placed in a knapsack with a fixed capacity, allowing fractions of items to be taken.

beginner

Why can we take fractions of items in the Fractional Knapsack Problem but not in the 0/1 Knapsack Problem?

Because the problem assumes items are divisible, like liquids or materials, allowing partial amounts to be taken, unlike 0/1 Knapsack where items are indivisible.

intermediate

What is the greedy strategy used in the Fractional Knapsack Problem?

Sort items by their value-to-weight ratio in descending order and take as much as possible from the highest ratio items first.

intermediate

In the Fractional Knapsack Problem, what happens if the knapsack capacity is less than the weight of the current item?

We take only the fraction of the item that fits into the remaining capacity to maximize value.

intermediate

What is the time complexity of the Fractional Knapsack Problem when using sorting?

O(n log n) due to sorting the items by value-to-weight ratio, where n is the number of items.

What is the key difference between Fractional Knapsack and 0/1 Knapsack?

A Both allow fractions of items

B 0/1 Knapsack allows fractions, Fractional Knapsack does not

C Neither allows fractions of items

D Fractional Knapsack allows taking parts of items, 0/1 Knapsack does not

Fractional Knapsack allows dividing items and taking fractions, unlike 0/1 Knapsack where items are either taken whole or not at all.

Which greedy criterion is used to select items in Fractional Knapsack?

A Highest value-to-weight ratio first

B Lowest value first

C Highest weight first

D Random selection

Items are chosen based on the highest value-to-weight ratio to maximize total value.

If the knapsack capacity is 50 and the next item weighs 70, what fraction of the item is taken?

A 0.5

B 1

C 0.714

D 0.7

Fraction taken = capacity / item weight = 50 / 70 ≈ 0.714.

What is the first step in solving the Fractional Knapsack Problem?

A Sort items by value-to-weight ratio descending

B Sort items by value descending

C Sort items by weight ascending

D Pick items randomly

Sorting by value-to-weight ratio descending ensures the greedy approach picks the most valuable items per unit weight first.

What is the overall time complexity of the Fractional Knapsack algorithm?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Sorting the items by value-to-weight ratio takes O(n log n), which dominates the algorithm's time complexity.

Explain the greedy approach used in the Fractional Knapsack Problem and why it works.

Think about choosing the most valuable parts first to fill the knapsack.

Describe how to handle an item that cannot fit fully into the remaining knapsack capacity in the Fractional Knapsack Problem.

Partial items are allowed, so take only what fits.