Fractional Knapsack Problem in DSA Go - Execution Trace

Concept Flow - Fractional Knapsack Problem

Start with empty knapsack

↓

Sort items by value/weight ratio

↓

For each item in sorted order

↓

Can whole item fit?

No→Take fraction to fill knapsack

|Yes↓

Add whole item to knapsack

↓

Knapsack full?

No→Next item

Yes↓

Done

We first sort items by their value per weight. Then we add whole items if they fit, or fractions if not, until the knapsack is full.

Execution Sample

DSA Go

items := []Item{{value: 60, weight: 10}, {value: 100, weight: 20}, {value: 120, weight: 30}}
capacity := 50
// Sort by value/weight
// Take items or fractions until capacity full

This code sorts items by value per weight and fills the knapsack with whole or fractional items to maximize value.

Execution Table

Step	Operation	Current Item (value, weight)	Weight Added	Fraction Taken	Total Weight	Total Value	Knapsack State
1	Sort items by value/weight	-	-	-	0	0	[]
2	Consider item 1	(60, 10)	10	1.0	10	60	[(60,10)]
3	Consider item 2	(100, 20)	20	1.0	30	160	[(60,10), (100,20)]
4	Consider item 3	(120, 30)	20	0.6667	50	240	[(60,10), (100,20), (80,20)]
5	Knapsack full	-	-	-	50	240	Final state

💡 Knapsack reached full capacity of 50 units, no more items can be added.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Total Weight	0	10	30	50	50
Total Value	0	60	160	240	240
Knapsack State	[]	[(60,10)]	[(60,10), (100,20)]	[(60,10), (100,20), (80,20)]	[(60,10), (100,20), (80,20)]

Key Moments - 3 Insights

Why do we take only a fraction of the last item instead of the whole?

Because adding the whole last item would exceed the knapsack capacity. We take only the fraction that fits, as shown in step 4 of the execution_table.

How do we decide the order of items to add?

We sort items by their value-to-weight ratio before adding, ensuring we pick the most valuable per weight first, as shown in step 1.

What happens if the knapsack capacity is larger than total weight of all items?

We add all items fully without fractions, and the knapsack won't be full. The process stops after all items are added.

Visual Quiz - 3 Questions

Look at the execution_table, what is the Total Value after adding the second item?

A 60

B 100

C 160

D 180

💡 Hint

Check the 'Total Value' column at Step 3 in the execution_table.

At which step does the knapsack become full?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Total Weight' column and see when it reaches capacity 50.

If the last item's weight was 10 instead of 30, what fraction would be taken at Step 4?

A 1.0 (whole item)

B 0.5

C 0.6667

D 0.0 (none)

💡 Hint

If the item fits fully within remaining capacity, fraction is 1.0 as per execution logic.

Concept Snapshot

Fractional Knapsack Problem:
- Sort items by value/weight ratio descending
- Add whole items if they fit
- Add fraction of item if not enough capacity
- Stop when knapsack is full
- Maximizes total value with fractional items allowed

Full Transcript

The Fractional Knapsack Problem fills a knapsack to maximize value. We first sort items by their value per weight. Then, we add whole items if they fit fully. If an item doesn't fit, we add only the fraction that fits. We stop when the knapsack is full. This approach ensures maximum total value. The execution table shows sorting, adding items, fractions taken, and final knapsack state. Key moments clarify why fractions are taken and how sorting affects the solution.

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