Fractional Knapsack Problem in DSA Go - Deep Dive

Overview - Fractional Knapsack Problem

What is it?

The Fractional Knapsack Problem is a way to choose items with weights and values to put into a bag with limited capacity. Unlike the 0/1 knapsack, you can take parts of items, not just whole ones. The goal is to maximize the total value in the bag without exceeding its weight limit. This problem helps us understand how to make the best choices when resources are limited.

Why it matters

This problem shows how to get the most value from limited space or resources, like packing a suitcase or loading a truck. Without this idea, we might waste space or miss out on valuable items. It teaches us how to make smart, flexible decisions when we can split things up. Many real-world problems, like resource allocation and budgeting, use this concept.

Where it fits

Before learning this, you should understand basic arrays, sorting, and greedy algorithms. After this, you can explore the 0/1 Knapsack Problem, dynamic programming, and optimization techniques. This topic fits in the journey of learning how to solve problems by making the best local choices step-by-step.

Mental Model

Core Idea

Pick items by value per weight, taking as much as fits, to maximize total value in limited space.

Think of it like...

Imagine filling a jar with different types of honey, each with a different sweetness per spoon. You want the sweetest jar possible, so you scoop the honey with the highest sweetness first, even if you only take a little of it.

Knapsack Capacity: 50 units
Items sorted by value/weight:
┌─────────────┬───────────┬───────────────┐
│ Item        │ Weight    │ Value/Weight  │
├─────────────┼───────────┼───────────────┤
│ Item A      │ 10        │ 60/10 = 6.0   │
│ Item B      │ 20        │ 100/20 = 5.0  │
│ Item C      │ 30        │ 120/30 = 4.0  │
└─────────────┴───────────┴───────────────┘
Fill knapsack:
[Take all of Item A (10 units)]
[Take all of Item B (20 units)]
[Take 20 units of Item C (partial)]
Total weight = 50 units
Total value = 60 + 100 + 80 = 240

Build-Up - 7 Steps

1

Foundation

Understanding the Knapsack Setup

Concept: Introduce the problem of choosing items with weights and values to fit into a limited bag.

Imagine you have a bag that can carry a limited weight, say 50 units. You have items, each with a weight and a value. Your goal is to fill the bag with items to get the highest total value without going over the weight limit. Unlike some problems, here you can take parts of items, not just whole ones.

Result

You understand the problem setup: limited capacity, items with weight and value, and the goal to maximize value.

Understanding the problem setup is key because it frames the challenge: balancing weight limits with value gain.

2

Foundation

Calculating Value per Weight Ratio

Concept: Learn to calculate how valuable each unit of weight is for every item.

For each item, divide its value by its weight to get the value per weight ratio. This tells you how much value you get for each unit of weight you carry. For example, an item worth 60 with weight 10 has a ratio of 6.0. This ratio helps decide which items to pick first.

Result

You can rank items by their value per weight ratio to prioritize which to take.

Knowing value per weight helps make smart choices by focusing on items that give the most value for the least weight.

3

Intermediate

Sorting Items by Value Density

🤔Before reading on: do you think sorting items by value per weight helps maximize total value? Commit to yes or no.

Concept: Sort items from highest to lowest value per weight to pick the best items first.

Sort the list of items so the one with the highest value per weight comes first. This way, when filling the bag, you always pick the most valuable items per unit weight first. This sorting is the core of the greedy approach.

Result

Items are ordered to maximize value gain when picking sequentially.

Sorting by value density ensures the greedy choice is optimal for fractional knapsack.

4

Intermediate

Greedy Selection of Items

🤔Before reading on: do you think taking whole items first or partial items first yields better total value? Commit to your answer.

Concept: Pick items in order, taking whole items if they fit, or partial if not, until the bag is full.

Start with the highest value per weight item. If it fits entirely, take it all. If not, take only the part that fits. Then move to the next item. Repeat until the bag is full. This greedy method guarantees the best total value for fractional knapsack.

Result

The bag is filled with items or parts of items maximizing total value within weight limit.

Understanding that partial items can be taken allows the greedy method to reach the best solution.

5

Intermediate

Implementing Fractional Knapsack in Go

Concept: Translate the greedy approach into runnable Go code with sorting and selection.

Define a struct for items with weight and value. Calculate value per weight. Sort items by this ratio descending. Loop through items, adding full or partial weights to the knapsack until capacity is reached. Print the total value and the fractions taken.

Result

A working Go program that outputs the maximum value and item fractions taken.

Seeing the algorithm in code solidifies understanding and shows practical application.

6

Advanced

Analyzing Time Complexity and Efficiency

🤔Before reading on: do you think sorting or selection dominates the time cost? Commit to your answer.

Concept: Understand the algorithm's performance and what affects its speed.

Sorting items by value per weight takes O(n log n) time. Selecting items is O(n). So overall, the algorithm runs in O(n log n). This is efficient for many practical uses. Knowing this helps decide if this method suits large datasets.

Result

You know the algorithm is efficient and what limits its speed.

Understanding time complexity helps predict performance and guides optimization.

7

Expert

Why Fractional Knapsack is Greedy Optimal

🤔Before reading on: do you think greedy always works for knapsack problems? Commit to yes or no.

Concept: Explain why the greedy approach guarantees the best solution only for fractional knapsack.

Because you can take fractions, picking the highest value per weight first always leads to the best total value. If you couldn't take fractions (0/1 knapsack), greedy might fail. This is due to the problem's continuous nature, making it solvable by a greedy method.

Result

You understand the mathematical reason greedy works here but not in all knapsack variants.

Knowing the problem's structure explains why greedy is perfect here and prevents misapplying it elsewhere.

Under the Hood

The algorithm sorts items by their value-to-weight ratio. Then it iterates through the sorted list, adding as much of each item as possible to the knapsack. If the item fits entirely, it is added whole; if not, only the fraction that fits is added. This process continues until the knapsack is full. Internally, this uses a greedy strategy that always picks the locally best option, which leads to the global optimum because fractions are allowed.

Why designed this way?

The fractional knapsack problem was designed to model situations where items can be divided, like liquids or divisible goods. This allows a simple greedy solution, unlike the 0/1 knapsack which is harder and requires dynamic programming. The design reflects real-world needs for flexible resource allocation and efficient computation.

┌───────────────┐
│ Input Items   │
│ (weight, val) │
└──────┬────────┘
       │ Calculate value/weight
       ▼
┌───────────────┐
│ Sort Items by │
│ value/weight  │
└──────┬────────┘
       │ Iterate items
       ▼
┌─────────────────────────────┐
│ For each item:              │
│ - If fits, take whole       │
│ - Else take fraction        │
│ Add to knapsack             │
└──────┬──────────────────────┘
       │
       ▼
┌───────────────┐
│ Output total  │
│ value & parts │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does greedy always solve all knapsack problems optimally? Commit yes or no.

Common Belief: Greedy approach always gives the best solution for any knapsack problem.

Reality: Greedy works only for fractional knapsack where items can be split. For 0/1 knapsack, greedy can fail and dynamic programming is needed.

Why it matters: Using greedy for 0/1 knapsack leads to wrong answers and poor decisions in real applications.

Quick: Can you take more weight than the knapsack capacity if you take fractions? Commit yes or no.

Common Belief: Taking fractions means you can exceed the knapsack capacity by splitting items.

Reality: You cannot exceed the knapsack capacity; fractions are only taken to fill the remaining space exactly.

Why it matters: Misunderstanding this can cause incorrect implementations that break constraints.

Quick: Is sorting by value alone enough to solve fractional knapsack optimally? Commit yes or no.

Common Belief: Sorting items by their total value is enough to maximize knapsack value.

Reality: Sorting must be by value per weight, not total value, to maximize value within weight limits.

Why it matters: Sorting by total value can lead to suboptimal packing and lower total value.

Expert Zone

1

The fractional knapsack problem's greedy solution relies on the problem's continuous nature, which breaks down if items are indivisible.

2

In practice, floating-point precision can affect the fraction calculations, so careful handling is needed in implementations.

3

The problem can be extended to multiple knapsacks or constraints, where greedy no longer guarantees optimality.

When NOT to use

Do not use fractional knapsack greedy approach when items cannot be divided (0/1 knapsack). Instead, use dynamic programming or branch and bound methods. Also avoid it when multiple constraints or complex dependencies exist.

Production Patterns

Used in resource allocation where divisible goods exist, like bandwidth allocation, cutting raw materials, or portfolio optimization. Often combined with sorting and priority queues for efficient real-time decisions.

Connections

0/1 Knapsack Problem

Builds-on and contrasts with fractional knapsack

Understanding fractional knapsack helps grasp why 0/1 knapsack is harder and requires different algorithms.

Greedy Algorithms

Fractional knapsack is a classic example of greedy algorithm application

Studying this problem deepens understanding of when greedy methods yield optimal solutions.

Resource Allocation in Economics

Fractional knapsack models optimal allocation of divisible resources

Knowing this problem helps understand economic decisions about distributing limited divisible goods for maximum benefit.

Common Pitfalls

#1 Taking items without sorting by value per weight ratio.

Wrong approach:

items := []Item{{weight:10, value:60}, {weight:20, value:100}, {weight:30, value:120}}
// No sorting
for _, item := range items {
// take items in given order
}

Correct approach:

sort.Slice(items, func(i, j int) bool {
return float64(items[i].value)/float64(items[i].weight) > float64(items[j].value)/float64(items[j].weight)
})
for _, item := range items {
// take items in sorted order
}

Root cause:

Not sorting ignores the key greedy principle, leading to suboptimal total value.

#2 Taking full items even when they don't fit, exceeding capacity.

Wrong approach:

if currentWeight+item.weight <= capacity {
currentWeight += item.weight
totalValue += item.value
} else {
totalValue += item.value // wrong: taking full item anyway
currentWeight += item.weight
}

Correct approach:

if currentWeight+item.weight <= capacity {
currentWeight += item.weight
totalValue += item.value
} else {
remain := capacity - currentWeight
fraction := float64(remain) / float64(item.weight)
totalValue += item.value * fraction
currentWeight = capacity
}

Root cause:

Ignoring partial item taking breaks capacity constraint and correctness.

#3 Sorting by total value instead of value per weight.

Wrong approach:

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

Correct approach:

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

Root cause:

Sorting by total value ignores weight, leading to poor packing decisions.

Key Takeaways

Fractional Knapsack allows taking parts of items to maximize value within weight limits.

Sorting items by value per weight ratio is the key to the greedy solution's success.

Greedy approach works optimally here because items are divisible, unlike 0/1 knapsack.

Understanding the problem's constraints prevents common mistakes like ignoring partial items or sorting incorrectly.

This problem models real-world resource allocation where divisible goods must be optimally packed.

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