Fractional Knapsack Problem in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the value-to-weight ratio for each item.

DSA C++

double ratio = items[i].value [1] items[i].weight;

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division

Using addition or subtraction instead of division

The value-to-weight ratio is calculated by dividing the value by the weight.

2fill in blank

medium

Complete the code to sort items by their value-to-weight ratio in descending order.

DSA C++

sort(items.begin(), items.end(), [](const Item &a, const Item &b) { return a.ratio [1] b.ratio; });

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' which sorts ascending

Using equality or inequality operators incorrectly

To sort in descending order, use '>' to compare ratios.

3fill in blank

hard

Fix the error in the loop condition to process items until capacity is full or all items are considered.

DSA C++

for (int i = 0; i [1] n && capacity > 0; i++) {

Drag options to blanks, or click blank then click option'

A<=

B>=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>=' causes out-of-bounds

Using '>' or '<=' causes skipping items or infinite loops

The loop should run while i is less than n to avoid out-of-bounds errors.

4fill in blank

hard

Fill both blanks to correctly update total value and capacity after taking a fraction of an item.

DSA C++

totalValue += items[i].ratio * [1];
capacity -= [2];

Drag options to blanks, or click blank then click option'

Acapacity

Bitems[i].weight

Citems[i].value

DtotalValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using items[i].weight instead of capacity

Using items[i].value or totalValue incorrectly

We add ratio * capacity (value for the fraction taken using remaining capacity) and reduce capacity by capacity (equivalent to setting it to 0).

5fill in blank

hard

Fill all three blanks to correctly take the whole item if it fits in capacity.

DSA C++

if (items[i].weight <= capacity) {
    totalValue += items[i].[1];
    capacity -= items[i].[2];
} else {
    totalValue += items[i].ratio * [3];
    capacity = 0;
}

Drag options to blanks, or click blank then click option'

Avalue

Bweight

Ccapacity

Dratio

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing value and weight in updates

Using ratio or weight incorrectly in fraction calculation

If the whole item fits, add its full value and reduce capacity by its weight. Otherwise, add fraction value for remaining capacity.

Practice

1. What is the main goal of the Fractional Knapsack Problem?

easy

A. Maximize total value by taking fractions of items within weight limit

B. Maximize total value by taking whole items only

C. Minimize total weight of items selected

D. Find the minimum number of items to fill the knapsack

Solution

1. Step 1: Understand problem goal

   The fractional knapsack problem allows taking parts of items to maximize value within a weight limit.

2. Step 2: Compare options

   Maximize total value by taking fractions of items within weight limit correctly states maximizing value by fractions; others are about whole items or minimizing weight, which are incorrect.

3. Final Answer:

   Maximize total value by taking fractions of items within weight limit -> Option A

4. Quick Check:

   Fractional knapsack = maximize value with fractions [OK]

Hint: Fractional knapsack allows partial items for max value [OK]

Common Mistakes:

• Confusing fractional knapsack with 0/1 knapsack
• Thinking only whole items can be taken
• Assuming problem minimizes weight

2. Which of the following C++ code snippets correctly sorts items by value-to-weight ratio in descending order for fractional knapsack?

easy

A. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return a.weight > b.weight; });

B. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); });

C. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return a.value < b.value; });

D. std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.weight / a.value) > (b.weight / b.value); });

Solution

1. Step 1: Identify correct sorting criteria

   We must sort by value-to-weight ratio descending: (value/weight) high to low.

2. Step 2: Check each option

   std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); sorts by (value/weight) descending correctly. Others sort by wrong ratio or by value or weight alone.

3. Final Answer:

   std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); -> Option B

4. Quick Check:

   Sort by value/weight descending = std::sort(items.begin(), items.end(), [](auto &a, auto &b) { return (a.value / a.weight) > (b.value / b.weight); }); [OK]

Hint: Sort by value/weight ratio descending for greedy pick [OK]

Common Mistakes:

• Sorting by weight/value instead of value/weight
• Sorting ascending instead of descending
• Sorting by value or weight alone

3. What is the output of the following C++ code snippet for fractional knapsack?

struct Item { int value; int weight; };
std::vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
int W = 50;
// Assume items sorted by value/weight descending
float totalValue = 0;
int capacity = W;
for (auto &item : items) {
  if (item.weight <= capacity) {
    capacity -= item.weight;
    totalValue += item.value;
  } else {
    totalValue += item.value * ((float)capacity / item.weight);
    break;
  }
}
std::cout << totalValue << std::endl;

medium

A. 180

B. 220

C. 200

D. 240

Solution

1. Step 1: Calculate value/weight ratios and sort

   Ratios: 60/10=6, 100/20=5, 120/30=4. Sorted order: {60,10}, {100,20}, {120,30}.

2. Step 2: Pick items greedily until capacity 50

   Take first item fully: capacity=50-10=40, totalValue=60. Take second item fully: capacity=40-20=20, totalValue=60+100=160. Take third item fraction: fraction=20/30=2/3, value=120*(2/3)=80. Total value=160+80=240.

3. Final Answer:

   240 -> Option D

4. Quick Check:

   Sum values with fractions = 240 [OK]

Hint: Pick full items then fraction of next to fill capacity [OK]

Common Mistakes:

• Not sorting items by value/weight ratio
• Taking items in wrong order
• Incorrect fraction calculation

4. Identify the bug in this fractional knapsack code snippet:

float fractionalKnapsack(int W, std::vector<Item> &items) {
  std::sort(items.begin(), items.end(), [](auto &a, auto &b) {
    return (a.value / a.weight) > (b.value / b.weight);
  });
  float totalValue = 0;
  int capacity = W;
  for (auto &item : items) {
    if (item.weight < capacity) {
      capacity -= item.weight;
      totalValue += item.value;
    } else {
      totalValue += item.value * ((float)capacity / item.weight);
      break;
    }
  }
  return totalValue;
}

medium

A. Should use <= instead of < in if condition to include full item when equal

B. Sorting comparator divides integers causing integer division error

C. Capacity variable should be float, not int

D. Missing return statement at end of function

Solution

1. Step 1: Analyze if condition for full item inclusion

   The condition uses 'item.weight < capacity', so if weight equals capacity, it skips full inclusion and takes fraction.

2. Step 2: Correct condition to include full item when weight equals capacity

   Changing to 'item.weight <= capacity' allows taking full item if it fits exactly, which is correct behavior.

3. Final Answer:

   Should use <= instead of < in if condition to include full item when equal -> Option A

4. Quick Check:

   Use <= to include full item when weight equals capacity [OK]

Hint: Use <= to include full item when weight equals capacity [OK]

Common Mistakes:

• Using < instead of <= causing partial fraction unnecessarily
• Ignoring integer division in comparator (not an issue here)
• Wrong variable types for capacity

5. Given items with values and weights: {value: 40, weight: 2}, {value: 100, weight: 20}, {value: 50, weight: 10}, and knapsack capacity 25, what is the maximum value achievable using fractional knapsack?

hard

A. 160

B. 150

C. 155

D. 140

Solution

1. Step 1: Calculate value/weight ratios and sort items

   Ratios: - 40/2 = 20 - 100/20 = 5 - 50/10 = 5 Sorted order: {40,2}, {100,20}, {50,10} (40,2 first due to highest ratio)

2. Step 2: Pick items greedily until capacity 25

   Take first item fully: capacity=25-2=23, totalValue=40. Take second item fully: capacity=23-20=3, totalValue=40+100=140. Take third item fraction: fraction=3/10=0.3, value=50*0.3=15. Total value=140+15=155.

3. Step 3: Re-check sorting for tie in ratio

   Since second and third items have same ratio, order can be swapped. Try picking {40,2}, {50,10}, {100,20}: Take {40,2}: capacity=23, value=40 Take {50,10}: capacity=13, value=90 Take fraction of {100,20}: fraction=13/20=0.65, value=100*0.65=65 Total=40+50+65=155 (same)

4. Final Answer:

   155 -> Option C

5. Quick Check:

   Pick highest ratio items fully, fraction last = 155 [OK]

Hint: Sort by ratio, pick full items, fraction last to fill capacity [OK]

Common Mistakes:

• Not sorting by value/weight ratio correctly
• Picking items in wrong order
• Ignoring fractional part calculation