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

Recall & Review

beginner

What is the Fractional Knapsack Problem?

It is a problem where you have a knapsack with a weight limit and items with weights and values. You can take fractions of items to maximize the total value without exceeding the weight limit.

beginner

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

Because the problem allows breaking items into smaller parts, so you can take any fraction of an item. In 0/1 Knapsack, items are indivisible and must be taken whole or not at all.

beginner

What is the main strategy used to solve the Fractional Knapsack Problem?

Use a greedy approach: sort items by value per weight (value/weight) in descending order, then take as much as possible from the highest ratio items until the knapsack is full.

beginner

How do you calculate the value per weight ratio for an item?

Divide the item's value by its weight: ratio = value / weight. This ratio helps decide which items to pick first.

intermediate

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

The time complexity is O(n log n) because sorting the items by their value/weight ratio takes O(n log n), and then selecting items is O(n).

In the Fractional Knapsack Problem, what determines the order in which items are chosen?

A Value of items

B Weight of items

C Value per weight ratio of items

D Number of items

Items are chosen based on their value per weight ratio, highest first, to maximize total value.

Can you take a part of an item in the Fractional Knapsack Problem?

A Yes, fractions of items are allowed

B No, items must be taken whole

C Only if the item is light

D Only if the item has high value

The problem allows taking any fraction of an item to fill the knapsack optimally.

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

A Neither allow fractions

B 0/1 Knapsack allows fractions; Fractional does not

C Both allow fractions

D Fractional Knapsack allows breaking items; 0/1 does not

Fractional Knapsack allows taking parts of items, while 0/1 Knapsack requires whole items.

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

A Pick the heaviest item

B Sort items by value per weight ratio

C Pick the item with highest value

D Pick items randomly

Sorting by value per weight ratio helps pick the most valuable items first.

What is the time complexity of the Fractional Knapsack solution?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Sorting the items takes O(n log n), which dominates the time complexity.

Explain how the greedy approach works in the Fractional Knapsack Problem.

Think about choosing the most valuable parts first.

Describe the difference between Fractional Knapsack and 0/1 Knapsack problems.

Focus on item divisibility and solution methods.