貪欲法 （greedy algorithm）
貪欲法 （greedy algorithm）は最適化手法の一つで、計算の各段階で最も良い部分解を計算していき、その部分解を組み合わせたものを最終解とする方法です。問題の内容によっては最適解であることが保証されますが、問題の内容によっては最適解である保証がないときもあります。
課題３３：貪欲法
財布の中に500円玉が n1 枚、100円玉が n2 枚、5０円玉が n3 枚、1０円玉が n4 枚、5円玉が n5 枚、1円玉が n6 枚あります。できるだけ少ない枚数の硬貨で、お釣りなしで x 円を支払いたいとき、必要な硬貨の枚数を返す関数を作ってください。そのような支払い方ができない場合は False を返してください。
ただし、
- 0 ≤ n1 ≤ 10
- 0 ≤ n2 ≤ 10
- 0 ≤ n3 ≤ 10
- 0 ≤ n4 ≤ 10
- 0 ≤ n5 ≤ 10
- 0 ≤ n6 ≤ 10
- 0 ≤ x ≤ 104
とします。
- 例1
x = 1672
9
- 例2
x = 5549
24
- 例3
x = 3067
11
- 例4
x = 8802
False
- 例5
x = -124
False
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。