Greedy vs DP How to Know Which to Apply in DSA Go - Build Both Approaches

Greedy vs Dynamic Programming: How to Know Which to Apply

📖 Scenario: Imagine you are organizing a small event and need to decide how to allocate your budget to buy snacks. You want to maximize the total tastiness of snacks you can buy without exceeding your budget. You have a list of snack options with their prices and tastiness scores.This project will help you understand when to use a simple greedy approach and when to use dynamic programming to solve such problems.

🎯 Goal: You will create a Go program that first tries a greedy approach to pick snacks by tastiness-to-price ratio, then uses dynamic programming to find the best combination of snacks within the budget. You will compare the results to see which method works better.

📋 What You'll Learn

Create a list of snacks with exact prices and tastiness values

Set a budget limit as a configuration variable

Implement a greedy algorithm to select snacks based on tastiness-to-price ratio

Implement a dynamic programming solution to select snacks maximizing tastiness within budget

Print the total tastiness and selected snacks for both methods

💡 Why This Matters

🌍 Real World

Budget allocation problems like shopping, resource management, and scheduling often require choosing the best combination of items under constraints.

💼 Career

Understanding when to use greedy algorithms versus dynamic programming is essential for software engineers solving optimization problems efficiently.

1

Create the snack list

Create a slice of structs called snacks where each snack has name (string), price (int), and tastiness (int). Add these exact snacks: {"Chips", 4, 7}, {"Chocolate", 5, 10}, {"Cookies", 3, 6}, {"Soda", 2, 4}, {"Fruit", 6, 8}.

DSA Go

// Define the Snack struct and create the snacks slice with given values
// Your code here

Hint

Define a struct named Snack with fields name, price, and tastiness. Then create a slice snacks with the exact snack entries.

2

Set the budget limit

Create an integer variable called budget and set it to 10.

DSA Go

package main

type Snack struct {
	name      string
	price     int
	tastiness int
}

func main() {
	snacks := []Snack{
		{"Chips", 4, 7},
		{"Chocolate", 5, 10},
		{"Cookies", 3, 6},
		{"Soda", 2, 4},
		{"Fruit", 6, 8},
	}
	// Create budget variable and set to 10
	// Your code here
}

Hint

Just create a variable named budget and assign it the value 10.

3

Implement the greedy snack selection

Write code to select snacks greedily by tastiness-to-price ratio. Create a slice selectedGreedy to hold chosen snacks. Sort snacks by tastiness/price descending. Then pick snacks in order if their price fits in remaining budget. Use variables remainingBudget and totalTastinessGreedy to track budget and tastiness.

DSA Go

package main

import "sort"

func main() {
	snacks := []Snack{
		{"Chips", 4, 7},
		{"Chocolate", 5, 10},
		{"Cookies", 3, 6},
		{"Soda", 2, 4},
		{"Fruit", 6, 8},
	}
	budget := 10

	// Implement greedy snack selection by tastiness/price ratio
	// Your code here
}

Hint

Sort the snacks by tastiness divided by price in descending order. Then pick snacks while you have budget left, updating the total tastiness and remaining budget.

4

Implement dynamic programming and print results

Implement a dynamic programming solution to find the maximum tastiness within budget. Use a 2D slice dp where dp[i][j] is max tastiness using first i snacks with budget j. Then backtrack to find selected snacks in selectedDP. Finally, print total tastiness and snack names for both greedy and DP methods exactly as: "Greedy total tastiness: X", "Greedy selected snacks: name1, name2", "DP total tastiness: Y", "DP selected snacks: nameA, nameB".

DSA Go

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	type Snack struct {
		name      string
		price     int
		tastiness int
	}

	snacks := []Snack{
		{"Chips", 4, 7},
		{"Chocolate", 5, 10},
		{"Cookies", 3, 6},
		{"Soda", 2, 4},
		{"Fruit", 6, 8},
	}
	budget := 10

	sort.Slice(snacks, func(i, j int) bool {
		ratioI := float64(snacks[i].tastiness) / float64(snacks[i].price)
		ratioJ := float64(snacks[j].tastiness) / float64(snacks[j].price)
		return ratioI > ratioJ
	})

	remainingBudget := budget
	totalTastinessGreedy := 0
	selectedGreedy := []Snack{}

	for _, snack := range snacks {
		if snack.price <= remainingBudget {
			selectedGreedy = append(selectedGreedy, snack)
			remainingBudget -= snack.price
			totalTastinessGreedy += snack.tastiness
		}
	}

	// Implement DP to find max tastiness within budget

	// Your code here
}

Hint

Use a 2D slice dp to store max tastiness for each snack count and budget. Then backtrack to find which snacks were chosen. Finally, print the results exactly as instructed.

Practice

1. Which of the following best describes when to use a greedy algorithm instead of dynamic programming?

easy

A. When the problem requires exploring all possible solutions

B. When the problem is unsolvable by any algorithm

C. When the problem has overlapping subproblems but no optimal substructure

D. When the problem has the greedy choice property and optimal substructure

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm works when choosing the best option at each step leads to a global optimum.

2. Step 2: Check optimal substructure

   Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

3. Final Answer:

   When the problem has the greedy choice property and optimal substructure -> Option D

4. Quick Check:

   Greedy = greedy choice + optimal substructure [OK]

Hint: Use greedy if local best leads to global best [OK]

Common Mistakes:

• Confusing overlapping subproblems with greedy applicability
• Using greedy when problem needs full exploration
• Ignoring optimal substructure requirement

2. Which Go code snippet correctly declares a memoization map for dynamic programming?

easy

A. memo := new(map[int]int)

B. memo := make(map[int]int)

C. memo := map[]int{}

D. memo := []int{}

Solution

1. Step 1: Understand Go map declaration

   In Go, maps are declared with make(map[keyType]valueType) to initialize properly.

2. Step 2: Check each option

   memo := make(map[int]int) uses make with correct syntax. memo := []int{} is a slice, not a map. memo := map[]int{} has invalid syntax. memo := new(map[int]int) uses new which returns pointer, not initialized map.

3. Final Answer:

   memo := make(map[int]int) -> Option B

4. Quick Check:

   Use make(map[key]value) for maps [OK]

Hint: Use make(map[key]value) to create maps in Go [OK]

Common Mistakes:

• Using new(map[int]int) which returns nil map pointer
• Confusing slices with maps
• Incorrect map syntax like map[]int{}

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    weights := []int{1, 3, 4, 5}
    values := []int{1, 4, 5, 7}
    capacity := 7
    dp := make([]int, capacity+1)

    for i := 0; i < len(weights); i++ {
        for w := capacity; w >= weights[i]; w-- {
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i])
        }
    }
    fmt.Println(dp[capacity])
}

medium

A. 12

B. 10

C. 11

D. 9

Solution

1. Step 1: Understand the code - 0/1 Knapsack DP

   The code uses bottom-up DP to find max value for capacity 7 with given weights and values.

2. Step 2: Trace DP array updates

   Items: (1,1), (3,4), (4,5), (5,7). DP updates from capacity down to weight. Final dp[7] = max value achievable is 11.

3. Final Answer:

   11 -> Option C

4. Quick Check:

   DP knapsack max value = 11 [OK]

Hint: Trace DP from largest capacity down to weight [OK]

Common Mistakes:

• Iterating w from low to high causing wrong results
• Confusing weights and values arrays
• Forgetting to update dp[w] with max

4. Identify the bug in this greedy approach for coin change problem in Go:

func coinChange(coins []int, amount int) int {
    count := 0
    for _, coin := range coins {
        count += amount / coin
        amount %= coin
    }
    if amount != 0 {
        return -1
    }
    return count
}

func main() {
    coins := []int{1, 3, 4}
    amount := 6
    fmt.Println(coinChange(coins, amount))
}

medium

A. Coins slice is not sorted descending

B. Using integer division causes wrong count

C. No base case for amount zero

D. Returns -1 even if solution exists

Solution

1. Step 1: Analyze greedy coin change logic

   The greedy approach works only if coins are sorted descending to pick largest coin first.

2. Step 2: Check coins order

   Coins are {1,3,4} ascending, so greedy picks 1 first, leading to wrong minimal count.

3. Final Answer:

   Coins slice is not sorted descending -> Option A

4. Quick Check:

   Sort coins descending for greedy coin change [OK]

Hint: Sort coins descending before greedy coin change [OK]

Common Mistakes:

• Not sorting coins descending
• Assuming greedy always works for coin change
• Ignoring leftover amount check

5. You want to find the minimum number of coins to make amount 11 using coins {1, 5, 6}. Which approach is best and why?

hard

A. Dynamic Programming, because greedy fails due to no greedy choice property

B. Greedy, because coins are sorted ascending

C. Greedy, because picking largest coin first always works

D. Neither, because problem is unsolvable

Solution

1. Step 1: Check greedy choice property for coin set

   For coins {1,5,6}, greedy picks 6 then 5, total 2 coins for 11, which is minimal. However, greedy does not always work for all amounts with these coins.

2. Step 2: Consider counterexamples and DP suitability

   In some cases greedy fails (e.g., amount 7 with coins {1,5,6} greedy picks 6+1=2 coins but better is 1+1+5=3 coins, so greedy works here but not always. DP always finds minimal coins by exploring all subproblems.

3. Final Answer:

   Dynamic Programming, because greedy fails due to no greedy choice property -> Option A

4. Quick Check:

   Use DP if greedy choice property missing [OK]

Hint: Use DP if greedy choice property is missing [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring overlapping subproblems in coin change
• Choosing greedy because coins are sorted ascending