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

質問

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

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

回答No.7

uminezumi

参考ＵＲＬに同じ問題と、動的計画法による解法の手順があります。
９ー４のダイナミックプログラミングという項目です。
ご参考までに。

http://www5c.biglobe.ne.jp/~MOGI/algorithm/algorithm09b.htm

参考URL：

http://www5c.biglobe.ne.jp/~MOGI/algorithm/algorithm09b.htm

回答No.6

mmky

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

回答No.5

TK0318

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

補足

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

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

回答No.4

mmky

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

「２０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

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

回答No.2

uminezumi

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

回答No.1

TK0318

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

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

補足

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