錬金マスター
2009.09.07 22:37 パソコン甲子園 2009
パソコン甲子園2009予選 問題07 錬金マスター
レシピの連鎖にサイクルが無いので、再帰で最小コストを求めることができます。
問題の仕様は残念ながら簡単化されていて(難易度調整のためでしょう)、サイズが小さく、作るものも1つ、1つのアイテムを作るレシピはたかだか1つしかないので、メモする(動的計画法にする)必要もないようです。
以下のプログラムは1つのアイテムが複数のレシピを持てるようにしてあります。
名前、値段、レシピのリストを持つ Item クラスを作ります。
getCost( stirng name ) で名前が nameである アイテム item を作る最小のコストを求めます。
最小のコストは以下のうち小さい方になります:
この問題の仕様ではレシピが1つしかないので、以下のうち小さい方を選べばよい:
問題はこちら。
レシピの連鎖にサイクルが無いので、再帰で最小コストを求めることができます。
問題の仕様は残念ながら簡単化されていて(難易度調整のためでしょう)、サイズが小さく、作るものも1つ、1つのアイテムを作るレシピはたかだか1つしかないので、メモする(動的計画法にする)必要もないようです。
以下のプログラムは1つのアイテムが複数のレシピを持てるようにしてあります。
名前、値段、レシピのリストを持つ Item クラスを作ります。
getCost( stirng name ) で名前が nameである アイテム item を作る最小のコストを求めます。
最小のコストは以下のうち小さい方になります:
- item のコスト
- item を作るレシピの中でコストが最小のものであるコスト
この問題の仕様ではレシピが1つしかないので、以下のうち小さい方を選べばよい:
- item のコスト
- item をレシピで作る(ある場合は)コスト
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |