エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
ナップサック問題 - ピコピコの日記
■ダイナミックプログラミング(動的計画法)とは 最適化問題を解くのに効果的な方法。 具体的には、n個... ■ダイナミックプログラミング(動的計画法)とは 最適化問題を解くのに効果的な方法。 具体的には、n個の要素に関する問題の最適解を求めるのに、部分集合であるi個の問題の最適解を覚えておき、 i個から1つ要素を増やした場合、覚えておいた最適解が変化するを調べる。 変化した場合は、それを最適解とし、最終的にn個の問題の最適解を見つけることができるというものだ。 ■ナップサック問題 ダイナミックプログラミングの代表的な例題。 入れることのできる重さが決まっているナップサックに、どれだけ無駄がなく詰めきれるかというもの。 今回は、重さと値段があるデータについて、なるべくナップサックの中身が高価格になるようにつめる という問題に取り組むことにした。 下記がソースです。 ただ、ちょっと今日は忙しかったんで書きなぐった状態です。 気が向いたら、きれいに書きなおそうと思います。 #include <stdi