掲示板システム
ホーム
アクセス解析
カテゴリ
ログアウト
メモ化探索における大小関係 (ID:72853)
名前
ホームページ(ブログ、Twitterなど)のURL (省略可)
本文
ホウジョウウサギさんありがとうございます。 色々な疑問があるのですが、一番簡単な疑問を表現するならこんな問題になります。 田舎の冒険家のＡさんは露出した鉱脈を探し当てた。 そこそこ珍重される鉱石がごろごろしている。 これを背中に背負ったナップザックで持って帰るのだが、鉱石はたくさん持って帰りたいがあまり多いと値崩れして価値が下がってしまう。 鉱石は自然の造形が美術品として珍重されるのでＡさんが割って持って帰るわけにはいかない。 一つ一つ塊でナップザックに入れるしかないのだ。 売上はAさんが持って帰る鉱石の価値の総計xで決まり,-ax(x-b)となっている。 Ａさんの住んでいる地域は治安が悪いので盗まれる恐れもあり一度に売りさばきたい。 転がっている鉱石の数Ｎ個 転がっている鉱石の各々の重さＷiと価値Ｖｉ、ナップザックで持って帰れる重さの限界W、定数aとｂの値が情報として与えられる。 ナップザック問題の拡張として上記問題をとくにはどうすればよいだろうか？ という感じです。 非線形最適化問題について調べてみます。 この辺は難しそうなので学習も牛歩の歩みになりそうです。 tetrapodさんのソース今から読んでみます。 リンク先問題は何も考えずに解くと15！の探索ということになりメモ化探索や工夫なしでは時間切れで不正解になるのですがその辺大丈夫でしょうか？
←解決時は質問者本人がここをチェックしてください。
更新する
戻る
掲示板システム
Copyright 2021 Takeshi Okamoto All Rights Reserved.