3.3 Greedy

1. What It Is

• At each step, make the best choice under the current state (a local optimum), hoping to derive a global optimum

2. Examples

2.1. Optimal Loading

2.1.1. Idea

• Select the lightest item each time and load it onto the ship

2.1.2. Implementation

import (
	"fmt"
	"sort"
)

func Pirate() {
	weight := []int{3, 5, 4, 10, 7, 14, 2, 11}
	sort.Ints(weight)
	remainWeight := 30
	result := make([]int, 0)
	for _, w := range weight {
		remainWeight -= w
		if remainWeight < 0 {
			break
		}
		result = append(result, w)
	}
	fmt.Println(result)
}

2.1.2.1. Test

func TestPirate(t *testing.T) {
	Pirate()
}

2.2. Coin Change

• Suppose there are 25-cent, 10-cent, 5-cent, and 1-cent coins. To give a customer 41 cents in change, how can we use the fewest coins?

2.2.1. Idea

• Select the coin with the largest denomination each time

2.2.2. Implementation

import (
	"fmt"
	"sort"
)

func CoinChange() {
	coinFace := []int{25, 10, 5, 1}
	changeMoney := 41
	sort.Slice(coinFace, func(i, j int) bool {
		return coinFace[i] > coinFace[j]
	})

	result := make([]int, 0)
	for i := 0; i < len(coinFace); i++ {
		if changeMoney-coinFace[i] < 0 {
			continue
		} else {
			changeMoney -= coinFace[i]
			result = append(result, coinFace[i])
			i--
		}

	}

	fmt.Println(result)
}

2.2.3. Test

func TestCoinChange(t *testing.T) {
	CoinChange()
}

2.3. 0-1 Knapsack

• 

2.3.1. Idea

• This example tries selecting the item with the largest value each time, but for the general 0-1 knapsack problem this does not guarantee the global optimum

2.3.2. Implementation

import (
	"fmt"
	"sort"
)

type Article struct {
	// Weight
	weight int
	// Value
	value int
}

func (a *Article) String() string {
	return fmt.Sprintf("[w%v:v%v]", a.weight, a.value)
}

func NewArticle(weight int, value int) *Article {
	return &Article{weight: weight, value: value}
}

func Knapsack() {
	articles := []*Article{
		NewArticle(35, 10),
		NewArticle(30, 40),
		NewArticle(60, 30),
		NewArticle(50, 50),
		NewArticle(40, 35),
		NewArticle(10, 40),
		NewArticle(25, 30),
	}
	sort.Slice(articles, func(i, j int) bool {
		return articles[i].value > articles[j].value
	})

	result := make([]*Article, 0)
	remainWeight := 150
	for _, a := range articles {
		if remainWeight-a.weight < 0 {
			continue
		}
		remainWeight -= a.weight
		result = append(result, a)
	}

	fmt.Println(result)
}

2.3.2.1. Test

func TestKnapsack(t *testing.T) {
	Knapsack()
}

3. References

• Greedy Algorithms and Divide-and-Conquer Examples - CSDN
• Sorting Custom Types in Go - SegmentFault