Fractional Knapsack Problem in DSA Go - Build from Scratch

Fractional Knapsack Problem

📖 Scenario: You are helping a delivery company pack valuable items into a knapsack. Each item has a weight and a value. The knapsack can carry a limited weight. You want to maximize the total value packed. You can take fractions of items if needed.

🎯 Goal: Build a program that calculates the maximum value that fits into the knapsack using the fractional knapsack approach.

📋 What You'll Learn

Create a slice of items with exact weights and values

Add a variable for the knapsack capacity

Implement the fractional knapsack logic using sorting and greedy selection

Print the maximum value packed with two decimal places

💡 Why This Matters

🌍 Real World

This problem models packing valuable goods efficiently into limited space, like cargo loading or resource allocation.

💼 Career

Understanding greedy algorithms and optimization is useful for software engineers working on logistics, finance, or resource management systems.

1

Create the items slice

Create a slice called items of structs with fields weight and value. Add these exact items: weight 10, value 60; weight 20, value 100; weight 30, value 120.

DSA Go

// Define the item struct and create the items slice with given weights and values
// Your code here

Hint

Define a struct with weight and value fields. Then create a slice with the exact items.

2

Add knapsack capacity variable

Add a variable called capacity of type float64 and set it to 50.

DSA Go

package main

type item struct {
    weight float64
    value  float64
}

func main() {
    items := []item{
        {weight: 10, value: 60},
        {weight: 20, value: 100},
        {weight: 30, value: 120},
    }
    // Add capacity variable here
    // Your code here
}

Hint

Use capacity := 50.0 to set the knapsack capacity.

3

Implement fractional knapsack logic

Implement the fractional knapsack logic: sort items by value-to-weight ratio in descending order, then pick items greedily to maximize value. Use variables totalValue and remainingCapacity to track progress.

DSA Go

package main

type item struct {
    weight float64
    value  float64
}

func main() {
    items := []item{
        {weight: 10, value: 60},
        {weight: 20, value: 100},
        {weight: 30, value: 120},
    }
    capacity := 50.0

    // Sort items by value/weight ratio descending
    // Use totalValue and remainingCapacity variables
    // Your code here
}

Hint

Sort by value/weight ratio descending. Then loop over items, add full or fractional value until capacity is full.

4

Print the maximum value

Print the totalValue with two decimal places using fmt.Printf.

DSA Go

package main

import (
    "fmt"
    "sort"
)

type item struct {
    weight float64
    value  float64
}

func main() {
    items := []item{
        {weight: 10, value: 60},
        {weight: 20, value: 100},
        {weight: 30, value: 120},
    }
    capacity := 50.0

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

    totalValue := 0.0
    remainingCapacity := capacity

    for _, it := range items {
        if remainingCapacity == 0 {
            break
        }
        if it.weight <= remainingCapacity {
            totalValue += it.value
            remainingCapacity -= it.weight
        } else {
            fraction := remainingCapacity / it.weight
            totalValue += it.value * fraction
            remainingCapacity = 0
        }
    }

    // Print totalValue with two decimals
    fmt.Printf("%.2f\n", totalValue)
}

Hint

Use fmt.Printf("%.2f\n", totalValue) to print the value with two decimals.

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