Fractional Knapsack Problem in DSA Go

Mental Model

We want to fill a bag with items to get the most value, and we can take parts of items if needed.

Analogy: Imagine you have a backpack and different jars of honey. Each jar has a weight and sweetness. You want to fill your backpack with the sweetest honey possible, even if you have to take only part of a jar.

Items: [weight: 10, value: 60] -> [weight: 20, value: 100] -> [weight: 30, value: 120]
Knapsack capacity: 50
Goal: Maximize value by taking whole or part of items.

Dry Run Walkthrough

Input: items: [(weight=10, value=60), (weight=20, value=100), (weight=30, value=120)], knapsack capacity=50

Goal: Fill knapsack with max total value, possibly taking fractions of items.

Step 1: Calculate value per weight for each item and sort items by this ratio descending

[Item1: 6.0] -> [Item2: 5.0] -> [Item3: 4.0]

Why: We want to pick items with highest value per weight first to maximize total value.

Step 2: Take whole Item1 (weight 10, value 60) into knapsack

Knapsack: 10/50 weight used, total value 60

Why: Item1 fits fully, so take it all to maximize value.

Step 3: Take whole Item2 (weight 20, value 100) into knapsack

Knapsack: 30/50 weight used, total value 160

Why: Item2 fits fully, so take it all next.

Step 4: Take fraction of Item3 to fill remaining capacity (20/30 of Item3)

Knapsack: 50/50 weight used, total value 160 + (20/30)*120 = 240

Why: Only 20 weight left, so take fraction of Item3 to fill knapsack fully.

Result:

Knapsack full: 50/50 weight used, total value 240

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type Item struct {
	weight float64
	value  float64
}

// FractionalKnapsack returns max value for given capacity
func FractionalKnapsack(items []Item, capacity float64) float64 {
	sort.Slice(items, func(i, j int) bool {
		return items[i].value/items[i].weight > items[j].value/items[j].weight
	})
	totalValue := 0.0
	for _, item := range items {
		if capacity == 0 {
			break
		}
		if item.weight <= capacity {
			totalValue += item.value
			capacity -= item.weight
		} else {
			fraction := capacity / item.weight
			totalValue += item.value * fraction
			capacity = 0
		}
	}
	return totalValue
}

func main() {
	items := []Item{{10, 60}, {20, 100}, {30, 120}}
	capacity := 50.0
	maxValue := FractionalKnapsack(items, capacity)
	fmt.Printf("Max value in knapsack: %.2f\n", maxValue)
}

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

Sort items by value per weight descending to pick best items first

for _, item := range items { if capacity == 0 { break }

Stop if knapsack is full

if item.weight <= capacity { totalValue += item.value; capacity -= item.weight }

Take whole item if it fits

else { fraction := capacity / item.weight; totalValue += item.value * fraction; capacity = 0 }

Take fraction of item to fill remaining capacity

Output

Max value in knapsack: 240.00

Complexity Analysis

Time: O(n log n) because we sort n items by value per weight

Space: O(1) because sorting is done in place and only a few variables used

vs Alternative: Better than trying all subsets (which is exponential), greedy approach is efficient and optimal for fractional knapsack

Edge Cases

Empty items list

Returns 0 value since no items to take

DSA Go

for _, item := range items { if capacity == 0 { break }

Knapsack capacity zero

Returns 0 value immediately

DSA Go

if capacity == 0 { break }

Item weight zero (invalid)

Division by zero avoided by problem constraints; if occurs, code may panic

DSA Go

No explicit guard; assumes positive weights

When to Use This Pattern

When you can take parts of items to maximize value under weight limit, use fractional knapsack greedy approach sorting by value/weight ratio.

Common Mistakes

Mistake: Sorting items by value only instead of value per weight
Fix: Sort items by value divided by weight to get best value density

Mistake: Trying to take whole items only, ignoring fractions
Fix: Allow taking fraction of item when remaining capacity is less than item weight

Summary

Find max total value by taking whole or fractional items within weight limit.

Use when items can be divided and you want max value in limited capacity.

Sort items by value per weight and greedily take best parts first.

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