Fractional Knapsack Problem in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fractional Knapsack Calculation

What is the maximum value returned by the fractional knapsack function for the given items and capacity?

DSA Go

package main
import "fmt"

type Item struct {
    value  float64
    weight float64
}

func fractionalKnapsack(items []Item, capacity float64) float64 {
    n := len(items)
    ratio := make([]float64, n)
    for i := 0; i < n; i++ {
        ratio[i] = items[i].value / items[i].weight
    }

    // Sort items by ratio descending (simple bubble sort for clarity)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if ratio[j] < ratio[j+1] {
                ratio[j], ratio[j+1] = ratio[j+1], ratio[j]
                items[j], items[j+1] = items[j+1], items[j]
            }
        }
    }

    totalValue := 0.0
    for i := 0; i < n; i++ {
        if capacity == 0 {
            break
        }
        if items[i].weight <= capacity {
            capacity -= items[i].weight
            totalValue += items[i].value
        } else {
            fraction := capacity / items[i].weight
            totalValue += items[i].value * fraction
            capacity = 0
        }
    }
    return totalValue
}

func main() {
    items := []Item{{value: 60, weight: 10}, {value: 100, weight: 20}, {value: 120, weight: 30}}
    capacity := 50.0
    fmt.Printf("%.2f", fractionalKnapsack(items, capacity))
}

A 240.00

B 220.00

C 180.00

D 200.00

💡 Hint

Calculate value/weight ratio and pick items starting from highest ratio until capacity is full.

The function sorts items by value-to-weight ratio descending. It picks whole items if possible, else a fraction of the last item to fill capacity. The maximum value is 240.00.

🧠 Conceptual

intermediate

Understanding Fractional Knapsack Approach

Why does the fractional knapsack problem allow taking fractions of items, unlike the 0/1 knapsack problem?

A Because the knapsack capacity is unlimited.

B Because items can be divided and partial value proportional to weight can be taken.

C Because the problem only considers integer weights.

D Because all items have the same weight and value.

💡 Hint

Think about what makes fractional knapsack different from 0/1 knapsack.

Fractional knapsack allows dividing items, so you can take any fraction of an item, gaining proportional value. This is why greedy approach works optimally.

🔧 Debug

advanced

Identify the Bug in Fractional Knapsack Sorting

What error will occur when running this code snippet for sorting items by value/weight ratio?

DSA Go

for i := 0; i < n-1; i++ {
    for j := 0; j < n-i-1; j++ {
        if ratio[j] > ratio[j+1] {
            ratio[j], ratio[j+1] = ratio[j+1], ratio[j]
            items[j], items[j+1] = items[j+1], items[j]
        }
    }
}

A Syntax error due to missing brackets.

B Runtime panic due to index out of range.

C The items will be sorted in ascending order of ratio, causing incorrect greedy selection.

D No error; code sorts items correctly.

💡 Hint

Check the comparison operator in the if condition for sorting order.

The code sorts ratios ascending because it swaps when ratio[j] > ratio[j+1]. Fractional knapsack requires descending order for correct greedy selection.

❓ Predict Output

advanced

Output of Fractional Knapsack with Zero Capacity

What is the output of the fractional knapsack function when the capacity is zero?

DSA Go

package main
import "fmt"

type Item struct {
    value  float64
    weight float64
}

func fractionalKnapsack(items []Item, capacity float64) float64 {
    totalValue := 0.0
    for _, item := range items {
        if capacity == 0 {
            break
        }
        if item.weight <= capacity {
            capacity -= item.weight
            totalValue += item.value
        } else {
            fraction := capacity / item.weight
            totalValue += item.value * fraction
            capacity = 0
        }
    }
    return totalValue
}

func main() {
    items := []Item{{value: 50, weight: 5}, {value: 100, weight: 10}}
    capacity := 0.0
    fmt.Printf("%.2f", fractionalKnapsack(items, capacity))
}

A Error: division by zero

B 50.00

C 100.00

D 0.00

💡 Hint

If capacity is zero, no items can be taken.

With zero capacity, the function breaks immediately and returns 0.00 value.

🧠 Conceptual

expert

Why Greedy Algorithm is Optimal for Fractional Knapsack

Why does the greedy algorithm guarantee an optimal solution for the fractional knapsack problem but not for the 0/1 knapsack problem?

A Because fractional knapsack allows dividing items, so picking highest value/weight ratio first always leads to optimal total value.

B Because 0/1 knapsack has fewer items to choose from.

C Because fractional knapsack has unlimited capacity.

D Because 0/1 knapsack sorts items by weight only.

💡 Hint

Consider the property of divisibility and how it affects the solution approach.

The greedy approach works optimally for fractional knapsack because items can be split, so taking the best ratio first maximizes value. For 0/1 knapsack, items are indivisible, so greedy fails.

Practice

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

easy

A. Find the item with the highest value only

B. Minimize the total weight of items selected

C. Select items without exceeding the number of items limit

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

Solution

1. Step 1: Understand the problem goal

   The fractional knapsack problem allows taking parts of items to maximize total value without exceeding weight capacity.

2. Step 2: Identify the correct objective

   The goal is to maximize value by possibly taking fractions, not just whole items or minimizing weight.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize value with fractions [OK]

Hint: Remember: fractional means partial items allowed [OK]

Common Mistakes:

• Thinking only whole items can be taken
• Confusing weight limit with item count limit
• Assuming minimizing weight is the goal

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

easy

A. sort.Slice(items, func(i, j int) bool { return items[i].value < items[j].value })

B. sort.Slice(items, func(i, j int) bool { return items[i].weight > items[j].weight })

C. sort.Slice(items, func(i, j int) bool { return items[i].value/items[i].weight > items[j].value/items[j].weight })

D. sort.Slice(items, func(i, j int) bool { return items[i].weight/items[i].value > items[j].weight/items[j].value })

Solution

1. Step 1: Identify sorting criteria for fractional knapsack

   Items must be sorted by value-to-weight ratio in descending order to pick the best value per weight first.

2. Step 2: Check each option's sorting logic

   sort.Slice(items, func(i, j int) bool { return items[i].value/items[i].weight > items[j].value/items[j].weight }) sorts by value/weight descending, which is correct. Others sort by weight or value incorrectly.

3. Final Answer:

   sort.Slice(items, func(i, j int) bool { return items[i].value/items[i].weight > items[j].value/items[j].weight }) -> Option C

4. Quick Check:

   Sort by value/weight descending = sort.Slice(items, func(i, j int) bool { return items[i].value/items[i].weight > items[j].value/items[j].weight }) [OK]

Hint: Sort by value/weight ratio descending for best picks [OK]

Common Mistakes:

• Sorting by weight only
• Sorting by value only
• Using ascending order instead of descending

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

type Item struct {
    value, weight float64
}

items := []Item{{60, 10}, {100, 20}, {120, 30}}
capacity := 50.0

// Sort by value/weight descending
sort.Slice(items, func(i, j int) bool {
    return items[i].value/items[i].weight > items[j].value/items[j].weight
})

var totalValue float64
for _, item := range items {
    if capacity == 0 {
        break
    }
    if item.weight <= capacity {
        capacity -= item.weight
        totalValue += item.value
    } else {
        fraction := capacity / item.weight
        totalValue += item.value * fraction
        capacity = 0
    }
}
fmt.Printf("%.2f", totalValue)

medium

A. 240.00

B. 220.00

C. 180.00

D. 200.00

Solution

1. Step 1: Sort items by value/weight ratio

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

2. Step 2: Pick items until capacity 50

   Take full {60,10} (capacity=40, value=60), full {100,20} (capacity=20, value=160), then fraction of {120,30} with 20 weight (fraction=20/30=2/3), value added=120*(2/3)=80, total=240.

3. Final Answer:

   240.00 -> Option A

4. Quick Check:

   Total value = 60 + 100 + 80 = 240.00 [OK]

Hint: Pick full items first, then fraction of last item [OK]

Common Mistakes:

• Not sorting by value/weight ratio
• Taking items without checking capacity
• Incorrect fraction calculation

4. Identify the bug in this Go code snippet for fractional knapsack and select the fix:

type Item struct {
    value, weight float64
}

items := []Item{{60, 10}, {100, 20}, {120, 30}}
capacity := 50.0

sort.Slice(items, func(i, j int) bool {
    return items[i].value > items[j].value
})

var totalValue float64
for _, item := range items {
    if capacity == 0 {
        break
    }
    if item.weight <= capacity {
        capacity -= item.weight
        totalValue += item.value
    } else {
        fraction := capacity / item.weight
        totalValue += item.value * fraction
        capacity = 0
    }
}
fmt.Printf("%.2f", totalValue)

medium

A. Change capacity to int type

B. Sort items by value/weight ratio descending instead of value only

C. Remove the fraction calculation

D. Use a for loop with index instead of range

Solution

1. Step 1: Analyze sorting criteria

   The code sorts by value only, which is incorrect for fractional knapsack; it should sort by value/weight ratio.

2. Step 2: Identify correct fix

   Sorting by value/weight ratio descending ensures maximum value per weight is chosen first, fixing the bug.

3. Final Answer:

   Sort items by value/weight ratio descending instead of value only -> Option B

4. Quick Check:

   Sort by value/weight ratio fixes selection [OK]

Hint: Sort by value/weight ratio, not just value [OK]

Common Mistakes:

• Sorting by value only
• Ignoring fraction calculation
• Changing variable types unnecessarily

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

hard

A. 140.00

B. 120.00

C. 150.00

D. 160.00

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}.

2. Step 2: Pick items until capacity 15

   Take full {40,2} (capacity=13, value=40), then full {50,10} (capacity=3, value=90), then fraction of {100,20} with 3 weight (fraction=3/20=0.15), value added=100*0.15=15, total=40 + 50 + 15=105.

3. Final Answer:

   105.00 -> Option A

4. Quick Check:

   Total value = 40 + 50 + 15 = 105.00 [OK]

Hint: Pick highest ratio items fully, then fraction last [OK]

Common Mistakes:

• Not sorting by value/weight ratio
• Taking heavier items first
• Incorrect fraction calculation