탐욕알고리즘(greedy algorithm)으로 풀어보는 (간단한) 음식 선택하기 - Golang version

greedy_algorithm.go

// From : https://www.edwith.org/datascience/lecture/33888/
// edwith에서 한글자막을 달아놓은 MIT의 Data Science 강좌중 첫번째 챕터입니다.
// 위 링크에서 파이썬 버전의 코드를 받아보실 수 있습니다.
// 칼로리가 제한될 때, 음식을 선택하는 문제를 탐욕 알고리즘으로 푸는 문제입니다.
// 파이썬 코드를 Golang으로 변환했습니다.

package main

import (
	"flag"
	"fmt"
	"sort"
)

// Food 구조체 정의
type Food struct {
	name     string
	value    float64
	calories float64
}

// Food 구조체에 바인딩하는 메소드
func (f *Food) getValue() float64 {
	return f.value
}

func (f *Food) getCost() float64 {
	return f.calories
}

func (f *Food) density() float64 {
	return f.getValue() / f.getCost()
}

// 메뉴 생성 메소드
func buildMenu(names []string, values []float64, calories []float64) []Food {
	menu := []Food{}
	for idx, value := range values {
		menu = append(menu, Food{names[idx], value, calories[idx]})
	}
	return menu
}

// greedy algorithm에 사용할 함수 작성
// switch구문으로 음식을 선택하는 기준을 지정 후 정렬
func greedy(items []Food, maxCost float64, keyString string) ([]Food, float64) {
	var menuCopy = make([]Food, len(items))
	copy(menuCopy, items)

	switch keyString {
	case "value":
		sort.Slice(menuCopy, func(i, j int) bool {
			return menuCopy[i].getValue() > menuCopy[j].getValue()
		})

	case "cost":
		sort.Slice(menuCopy, func(i, j int) bool {
			return (1 / menuCopy[i].getCost()) > (1 / menuCopy[j].getCost())
		})

	case "density":
		sort.Slice(menuCopy, func(i, j int) bool {
			return menuCopy[i].density() > menuCopy[j].density()
		})
	}

	result := []Food{}
	var totalValue float64
	var totalCost float64
	totalValue, totalCost = 0.0, 0.0
	for i := 0; i < len(menuCopy); i++ {
		if totalCost+menuCopy[i].getCost() <= maxCost {
			result = append(result, menuCopy[i])
			totalCost += menuCopy[i].getCost()
			totalValue += menuCopy[i].getValue()
		}
	}

	return result, totalValue
}

// greedy 메소드를 테스팅할 함수
func testGreedy(items []Food, constraint float64, keyString string) {
	taken, val := greedy(items, constraint, keyString)
	fmt.Println("Total value of items taken =", val)
	for idx := range taken {

		fmt.Printf("	%s <%d, %d>\n", taken[idx].name, int32(taken[idx].value), int32(taken[idx].calories))
	}
}

// value, cost, density 별 greedy 메소드를 적용할 
func testGreedys(foods []Food, maxUnits float64) {
	fmt.Printf("Use greedy by value to allocate %d calories\n\n", int32(maxUnits))
	testGreedy(foods, maxUnits, "value")

	fmt.Printf("Use greedy by cost to allocate %d calories\n\n", int32(maxUnits))
	testGreedy(foods, maxUnits, "cost")

	fmt.Printf("Use greedy by density to allocate %d calories\n\n", int32(maxUnits))
	testGreedy(foods, maxUnits, "density")
}

func main() {
	//greedy algorithm을 이용한 제한된 칼로리내에서 음식 메뉴 결정하기

	// 값 초기화
	const (
		defaultConstraint = 1000.0
	)

	var constraint float64
	flag.Float64Var(&constraint, "constraint", defaultConstraint, "Constraint value about Calorie")

	flag.Parse()

	names := []string{
		"wine",
		"beer",
		"pizza",
		"burger",
		"fries",
		"cola",
		"apple",
		"donut",
	}

	values := []float64{
		89.0,
		90.0,
		95.0,
		100.0,
		90.0,
		79.0,
		50.0,
		10.0,
	}

	calories := []float64{
		123.0,
		154.0,
		258.0,
		354.0,
		365.0,
		150.0,
		95.0,
		195.0,
	}

	foods := buildMenu(names, values, calories)

	testGreedys(foods, constraint)
}