条件付の組み合わせ最適問題教えて下さい

質問

ヨウジと申します。20代後半の技術職です。

すみません、数学の組み合わせ最適問題について教えてください。
ナップザック問題の派生のような感じなのですが。

ナップザックにN個荷物を入れるが、荷物はN種類のジャンルから1つずつ入れないといけない。
N種類のジャンルにはそれぞれ複数個の候補の荷物があり、それぞれ重さ、価値が決まっている。このとき、

(1)ナップザックに入れられる物の重さは制限以下にしたい。（M以下）
(2)ナップザックに入れる物の価値は出来るだけ高くしたい。
(3)ナップザックに入れる際に、各ジャンルから1つずつ荷物を入れる。

という条件で、最適組合せを求めるやり方を教えて頂きたいのです。
線型計画法とか、Genetic Algorithmとかで解くのかなと思いますが、
どうも、年のせいか、数学がわからなくなってしまいまして。

よろしくお願いします。

回答No.1

rinri503

価格ｘ個数＝価格のように関係式が立てられるときは線形数学のように数学で解けますが、個数は１コと固定していますから、はかりに制限重量のおもりをつけ各品物の最軽量のものをとりあえず１コずつ載せ、品物ごとに取り替え価値をたかめるしか方法がないのでは

お礼

どうもありがとうございます。
助かりました。