Fractional Knapsack Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

What is the output of the following C++ code that calculates the maximum value for the fractional knapsack problem?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int value, weight;
};

bool cmp(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

double fractionalKnapsack(int W, vector<Item> &items) {
    sort(items.begin(), items.end(), cmp);
    double totalValue = 0.0;
    for (auto &item : items) {
        if (W == 0) break;
        if (item.weight <= W) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)W / item.weight);
            W = 0;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50;
    cout << fractionalKnapsack(W, items) << endl;
    return 0;
}

A 180

B 240

C 220

D 200

💡 Hint

Sort items by value/weight ratio and take as much as possible from highest ratio first.

The items sorted by value/weight ratio are (60/10=6), (100/20=5), (120/30=4). Taking full 10 weight of first item adds 60 value, full 20 weight of second adds 100 value, and remaining 20 weight fraction of third adds 120*(20/30)=80 value. Total = 60+100+80=240.

🧠 Conceptual

intermediate

Understanding Fractional Knapsack Strategy

Why does the fractional knapsack problem use a greedy approach based on value-to-weight ratio?

A Because taking items randomly ensures fairness and maximum value.

B Because sorting items by weight alone guarantees maximum value.

C Because the problem requires dynamic programming to find the best solution.

D Because taking items with highest value-to-weight ratio first maximizes total value efficiently.

💡 Hint

Think about which items give the most value per unit weight.

The greedy approach works because taking items with the highest value per weight first ensures the knapsack is filled with the most valuable fractions possible, maximizing total value.

🔧 Debug

advanced

Identify the Bug in Fractional Knapsack Code

What error will the following code produce when compiled and run?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int value, weight;
};

bool cmp(Item a, Item b) {
    return a.value / a.weight > b.value / b.weight;
}

double fractionalKnapsack(int W, vector<Item> &items) {
    sort(items.begin(), items.end(), cmp);
    double totalValue = 0.0;
    for (auto &item : items) {
        if (W == 0) break;
        if (item.weight <= W) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)W / item.weight);
            W = 0;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50;
    cout << fractionalKnapsack(W, items) << endl;
    return 0;
}

A The code runs correctly and outputs 240

B The code outputs 0 due to integer division in comparator

C Compilation error due to missing return statement in cmp

D Runtime error due to division by zero

💡 Hint

Does integer division affect the sorting for these specific items? Check the ratios: 60/10=6, 100/20=5, 120/30=4.

For these items, the value/weight ratios are exact integers (6, 5, 4), so integer division produces the same comparison results as floating-point division. The sorting is correct, and the code outputs 240.

📝 Syntax

advanced

Syntax Error in Fractional Knapsack Code

Which option contains the syntax error that prevents compilation?

DSA C++

struct Item {
    int value, weight
};

bool cmp(Item a, Item b) {
    return (double)a.value / a.weight > (double)b.value / b.weight;
}

A Incorrect cast syntax in cmp function

B Missing return type in cmp function

C Missing semicolon after struct Item definition

D Missing parentheses in return statement

💡 Hint

Check punctuation after struct declarations.

In C++, struct definitions must end with a semicolon. Missing it causes a syntax error.

🚀 Application

expert

Maximum Value with Fractional Knapsack for Custom Items

Given items with values and weights: (40, 2), (100, 20), (50, 10), and knapsack capacity 25, what is the maximum value the fractional knapsack can hold?

A 155

B 160

C 180

D 140

💡 Hint

Calculate value/weight ratio for each item and take fractions accordingly.

Ratios: 40/2=20, 100/20=5, 50/10=5. Take full (40,2): value 40, rem 23. Take full (50,10): value 50, total value 90, rem 13. Fraction of (100,20): (13/20)*100 = 65. Total: 155. Alternatively, after (40,2), take full (100,20): value 100, total 140, rem 3, fraction (50,10): (3/10)*50=15, total 155.

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