多重ナップザック問題というらしいです。

下記のようにの品物の価値と重さが決まっている。
　品物　　　　　　重さ(kg)　　価格(円)
ルビー鉱石　　　　　４　　　　４５００
サファイヤ鉱石　　　５　　　　５７００
エメラルド鉱石　　　２　　　　２２５０
石炭　　　　　　　　　１　　　　１１００
ダイヤモンド鉱石　　６　　　　６７００
これを２０kgの重量制限がある袋に品物を選んで（重複しても良い）入れるとき
価格が最大になる組み合わせを動的計画法の形で定式化して解を求める道筋を説明しなさい。

どなたか教えてください。

No.7 回答者： uminezumi 回答日時： 2003/01/15 18:03

参考ＵＲＬに同じ問題と、動的計画法による解法の手順があります。

９ー４のダイナミックプログラミングという項目です。
ご参考までに。

http://www5c.biglobe.ne.jp/~MOGI/algorithm/algor …

参考URL：http://www5c.biglobe.ne.jp/~MOGI/algorithm/algor …

No.6 回答者： mmky 回答日時： 2003/01/15 16:33

やはり経済学の分析手法ですね。

Ｙａｈｏｏサイトでkeyword 「費用便益分析」+ 「ナップザ ック問題」 で検索してみてください。　参考になる論文があります。
参考まで

No.5 回答者： TK0318 回答日時： 2003/01/15 14:31

＃１です。

すいません、計算間違えていました＾＾；
サファイア４で２２８００円が正解です。

この回答への補足

回答ありがとうございます。

答えだけでなく動的計画法がわかる方いらっしゃいましたら教えてください。

補足日時：2003/01/15 14:57

No.4 回答者： mmky 回答日時： 2003/01/15 14:29

参考にならないかもしれませんが、皆さんに同じ

「２０kgの重量制限がある袋に品物を選んで（重複しても良い）入れるとき」 ということですから、一番（Kgあたりの価格）の高いものを選びますね。
重複しても良い場合は、以下の表からKgあたりの価格の高いものから選びます。当然、サファイヤを20Kgとなります。
重複が否定されれば、Kgあたりの価格の高いもの順に選びます。
違っているかな？


品目/・・・・重さkg・価格（円）・価格/kg
ルビー/・・・・・4・・・4500・・・1125
サファイヤ/・・5・・・5700・・・1140
エメラルド/・・2・・・2250・・・1125
石炭/・・・・・・1・・・1100・・・1100
ダイヤモンド/・6・・・6700・・・1117

No.3 回答者： ebinamori 回答日時： 2003/01/15 14:26

それぞれの１ｋｇ当たりの価格は

ルビー　　　　１１２５ｋｇ／ｙ　
サファイヤ　　１１４０ｋｇ／ｙ
エメラルド　　１１２５ｋｇ／ｙ
石炭　　　　　１１００ｋｇ／ｙ
ダイヤモンド　１１１６．６６ｋｇ／ｙ
これで見るとサファイヤが一番高価みたいなんで
高価なものを一番多くつむのは
サファイヤ×５×４＝２２８００円
になるのでこれが一番大きいような気がします。

No.2 回答者： uminezumi 回答日時： 2003/01/15 14:24

動的計画法は、専門の方におまかせするとして、サファイヤ４個で２２８００円になりますよ。

No.1 回答者： TK0318 回答日時： 2003/01/15 14:18

＞動的計画法の形で定式化

方法はさっぱり分からないけど虱つぶしで計算したら
ダイアモンド １ サファイア ２ エメラルド ２（ルビー １）
で２２６００円になりました。

・・・ところで問題あっていますか？
ルビー４ｋｇとエメラルド４ｋｇの値段が同じなのでルビーの存在意義がないのですが・・・

この回答への補足

回答ありがとうございます。問題はあってます。
想像ですがダイヤモンドと絡ませて20キロになる２kgの設定がほしかったのではないでしょうか？

補足日時：2003/01/15 14:55