Tech Tips

  1. プログラミング
  2. 647 view

[Algorithm]貪欲法

Contents

目的

greedy-ans1
以下の問題を貪欲法で解く.
できるだけ少ない枚数で指定された金額を支払う場合,何枚になるか.

貪欲法

greedy
その時々で最善と思われる行動を取る方法のこと.
利点は単純で計算速度が速く,最善の定義を問題に対して適切に設定するとそれなりに良い解が得られる.

貪欲法の問題への適用

単純に500円玉から順に使っていくだけ.
greedy-ans2
greedy-ans3
greedy-ans4
greedy-ans5

プログラム

package main

import (
  "fmt"
  "bufio"
  "os"
  "strconv"
  "strings"
)

// Standard Input Function
func Scan() string {
  reader := bufio.NewReader(os.Stdin)
  input, _ := reader.ReadString('\n')
  return strings.TrimRight(input, "\n")
}

// Min
func Min(v1, v2 int) int {
  if v1 > v2 { return v2
  } else     { return v1 }
}

func Solve(amount int, values [6]int, limits []int) int {
  answer := 0

  for i := 5; i >= 0; i-- {
    num := Min(amount / values[i], limits[i])
    amount -= num * values[i]
    answer += num
  }

  return answer
}

func main() {
  coinValue := [6]int{1, 5, 10, 50, 100, 500}
  coinLimit := make([]int, 6)

  fmt.Printf("Please input total amount to pay:")
  amount,_ := strconv.Atoi(Scan())

  for i := 0; i < 6; i++ {
    fmt.Printf("Please input limit number of %d yen:", coinValue[i])
    coinLimit[i], _ = strconv.Atoi(Scan())
  }

  fmt.Printf("Answer : %d\n", Solve(amount, coinValue, coinLimit))
}

実行結果

Please input total amount to pay:620
Please input limit number of 1 yen:3
Please input limit number of 5 yen:2
Please input limit number of 10 yen:1
Please input limit number of 50 yen:3
Please input limit number of 100 yen:0
Please input limit number of 500 yen:2
Answer : 6

プログラミングの最近記事

  1. PlatformIO IDE for VSCode を使用して VSCode で Ardu…

  2. ROS Docker イメージで発生した GPG error の解消方法

  3. Streamlit で訪れた国を色づけした世界地図を作成できるアプリケーションを作成してみ…

  4. M5Stack Core2 for AWS – ESP32 IoT開発キットで…

  5. D3.js v7 で点・線・テキスト・ツールチップ・ズームを設定する方法

関連記事

PAGE TOP