Fractional Knapsack MCQs: 12 Solved Questions with Explanations

Fractional Knapsack lets greedy win because items may be split. Its numeric drill is ratio, sort, fill, fraction. Attempt each MCQ before its explanation. Five are previous-year questions with direct links; use the Algorithms learn module for the remaining drills. This subtopic has about 15 questions available for practice.

Related reading: greedy algorithms and greedy and Huffman MCQs.

Which paradigm solves Fractional Knapsack? Questions 1 to 3

Divisibility makes greedy safe: swapping higher-ratio material into a solution improves its value. This argument fails for indivisible 0/1 items.

Q1. BPSC 2024

Fractional knapsack problem is solved most efficiently by which of the following algorithm?

(a) Backtracking

(b) Greedy algorithm

(c) Dynamic programming

(d) More than one of the above

(e) None of the above

Answer: (b) Greedy algorithm. Sort by ratio, then fill in one pass. Backtracking explores needless combinations. Dynamic programming costs more, so "most efficiently" eliminates option (d).

Q2. TPSC 2026

Which of the following problems can be solved using the greedy algorithm approach?

(a) 0/1 Knapsack problem

(b) Longest Common Subsequence

(c) Fractional Knapsack problem

(d) Matrix Chain Multiplication

Answer: (c) Fractional Knapsack problem. Its locally best fraction is globally safe. 0/1 knapsack needs include-or-exclude optimisation; LCS and matrix chain multiplication use overlapping subproblems. This three-DP-against-one-greedy pattern recurs in programmer exams.

Q3. Problem domain

To which of the following domain problem does the knapsack problem belong?

(a) NP-complete

(b) Sorting

(c) Optimization

(d) Linear Solution

Answer: (c) Optimization. Knapsack seeks the best feasible value under capacity. Sorting is only a solution step. The 0/1 decision version is NP-complete, but the stem asks for the domain, and the fractional variant is polynomial.

0/1 versus fractional: the divisibility line

In 0/1 knapsack, take an item whole or leave it; fractional knapsack permits any part. Divisibility makes greedy safe here. The 0/1 knapsack and dynamic programming primer covers the other case.

Q4. LTI Mindtree 2025

Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?

(a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible

(b) Both are the same

(c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming

(d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

Answer: (d). Option (a) swaps the definitions and (c) swaps the techniques. The names decode it: 0/1 means zero or one; fractional permits fractions.

The greedy drill and its cost: Questions 5 and 6

Compute ratios, sort descending, take whole items, then fill the gap with a fraction. Sorting dominates, as the sorting algorithms comparison explains.

Q5. Capacity 50

A thief has a knapsack of capacity 50. He can take items with the following (value, weight):

Item1: (60, 10)

Item2: (100, 20)

Item3: (120, 30)

What is the maximum value he can carry using the greedy fractional knapsack approach?

(a) 220

(b) 240

(c) 260

(d) 280

Answer: (b) 240. Ratios are 60/10 = 6, 100/20 = 5 and 120/30 = 4. Item1 and Item2 give weight 30, value 160. The remaining 20 units take 20/30 = 2/3 of Item3, adding 80. Total: 160 + 80 = 240. Option 280 needs weight 60. Under 0/1 rules, Item2 plus Item3 give 220, the trap in option (a).

Q6. Time complexity

The fractional knapsack problem can be solved in ______ time complexity using a greedy approach.

(a) O(n)

(b) O(log n)

(c) O(n²)

(d) O(n log n)

Answer: (d) O(n log n). Sorting costs O(n log n); filling is O(n). Option (a) counts only filling. Repeated scans could cost O(n²); nothing here is logarithmic.

Classic solved instances: capacity, ratios and fractions

Q7. UGC NET June 2014

Consider the fractional knapsack instance n = 4, (p1, p2, p3, p4) = (10, 10, 12, 18), (w1, w2, w3, w4) = (2, 4, 6, 9) and M = 15. The maximum profit is given by (Assume p and w denotes profit and weight of objects respectively)

(a) 40

(b) 38

(c) 32

(d) 30

Answer: (b) 38. Ratios are 5, 2.5, 2 and 2. Objects 1, 2 and 3 use weight 12 for profit 32. The final 3 units take 1/3 of object 4, adding 6. Taking object 4 before object 3 also gives 38, so ties do not matter. Option 32 skips the fraction; objects 1, 3 and 4 give 40 but weigh 17.

Q8. Decimal profit

Consider the following instance of a knapsack problem: Number of objects n = 4; knapsack capacity m = 35, profit (p1, p2, p3, p4) = (26, 22, 18, 20), weight (w1, w2, w3, w4) = (16, 18, 14, 20). The profit obtained in the optimal solution using Greedy approach is

(a) 50.11

(b) 62.4

(c) 45.6

(d) 49

Answer: (a) 50.11. Ratios are 1.625, 1.22, 1.29 and 1, ordering x1, x3, x2, x4. x1 and x3 give weight 30, profit 44. Then 5/18 of x2 adds 22 × 5/18 = 6.11. Total: 50.11; vector: (1, 5/18, 1, 0). Decimals often signal fractions.

Q9. Which object is partial?

Consider a Knapsack instance

i) Capacity of Knapsack is 15 and there are 7 objects

ii) profits (p1, p2, ..., p7) = 10, 5, 15, 7, 6, 18, 3

iii) weights (w1, w2, ..., w7) = 2, 3, 5, 7, 1, 4, 1

iv) Objects (x1, x2, x3, ..., x7)

Find which object is partially placed in the knapsack using profit/weight

(a) x1

(b) x2

(c) x3

(d) x4

Answer: (b) x2. Ratios are x1 = 5, x2 = 1.67, x3 = 3, x4 = 1, x5 = 6, x6 = 4.5 and x7 = 3. Items x5, x1, x6, x3 and x7 use weight 13. Only 2/3 of x2 fits next; x4 never enters. A fill simulation identifies the split item.

Bigger tables, same discipline

Q10. Capacity 20 with eight objects

The following Knapsack bag. The Knapsack bag maximum Capacity is 20. Find out the maximum profit for Fractional Knapsack____

(a) 165

(b) 171

(c) 180

(d) 192

Answer: (b) 171. Ratio order is T = 19, X = 10.7, R = 8.7, S = 6.7, Q = 6, P = 5, W = 3.3, V = 2.8. T, X, R, S and Q use weight 19 for profit 166. One quarter of P adds 5. Total: 171. Ratio, not raw profit, puts T first.

Q11. Numeric answer

For the following fractional knapsack instance, find the maximum possible value.

Capacity: 20 units

Known item data:

j: value = 4, weight = 1, value/weight = 4

d: value = 3, weight = 1, value/weight = 3

a: value = 7, weight = 3, value/weight = 7/3

e: value = 26, weight = 12, value/weight = 26/12

g: value = 18, weight = 9, value/weight = 2

The remaining available items have value/weight ratios no greater than 2: b = 2, f = 1.9, h ≈ 1.89, c = 1.5, and i = 1.25.

Enter the maximum value only.

Answer: 46. Take j, d, a and e whole: weight 1 + 1 + 3 + 12 = 17, value 4 + 3 + 7 + 26 = 40. Three units remain. The best ratio is 2, so 3/9 of g adds 6. Total: 46. With no options, trust the ratio order.

Where greedy breaks: the 0/1 trap

Q12. GATE 2018

Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt − Vgreedy is ____________.

Answer: 16. Ratios are Item4 = 12, Item1 = 6, Item3 = 5 and Item2 = 4. Greedy takes Item4, skips Item1, takes Item3, then cannot fit Item2: Vgreedy = 44. Item1 alone gives Vopt = 60. Rivals Items 2 + 4 give 52, Items 2 + 3 give 48, and Items 2 + 3 + 4 weigh 13. Therefore Vopt − Vgreedy = 16. Q5's ratio rule fails when splitting is banned.

The short version and your next step

• Fractional Knapsack uses greedy value-to-weight ordering.

• The drill is ratio, sort, fill and fraction.

• Sorting makes the complexity O(n log n).

• 0/1 items are indivisible and need dynamic programming; ratio ties do not alter a fractional optimum.

• On a 0/1 instance, ratio-greedy can lose to the optimal subset.

There are about 15 Fractional Knapsack questions available for practice. The five linked previous-year questions open in their source courses; the Algorithms learn module holds the remaining drills. Continue with GATE Guidance by Sanchit Sir, then browse GATE CS preparation options.