問題を正しく特定したかどうかはわかりませんが、ナップサック問題を読むことは、私が解決しようとしていることに最も近いようです。
料理人には、さまざまな量のいくつかの材料があります。例えば：
卵8個ソーセージ3個ミルク500mLイチゴ12個
レシピの有限のリストがあり、それぞれがさまざまな量のさまざまな材料で構成されています。すべてのレシピの各材料の量と同様に、材料の世界は有限です。
各レシピには、料理人が持っている材料が含まれている場合と含まれていない場合があります。
料理人は、1つのレシピの無駄を最小限に抑えるために、可能な限りすべての材料を使い果たしたいと考えています。
料理人が残り物を最小限に抑えて、2つまたは3つの異なるレシピですべての材料を使用したい場合があります。
彼の最適化されたソリューションは何ですか？
編集：私の質問は、次のナップサック問題のより複雑なバージョンです http://www.g12.cs.mu.oz.au/wiki/doku.php?id=simple_knapsack
あなたのQに何も欠けていなければ、これはナップザックの問題のようには聞こえません.各レシピに入れる各材料の量はわかっているので、スロットサイズは変数ではありません.
私があなたの Q を正しく読んだ場合、あなたがする必要があるのは、各レシピで材料を実行し、量が十分かどうかを確認することだけです。そのような正の値が最小のレシピが答えです。材料リストに直接アクセスするには\theta(m*n)時間かかります.m & nは材料とレシピの数です.
あなたの Q を書き直して、私が正しく理解しているか確認させてください: あなたは一連のレシピ S を持っており、それぞれに必要な材料のリストが含まれています。コックには一連の食材があり、その中には成分がゼロの場合もあります。いわゆる残り物を最小限に抑えながら、S の各レシピが料理人が持っている食材で満たされるように、S のサブセットを決定したいと考えています。
卵が1個、ソーセージが5個あるとします。2 つのレシピ: A. ソーセージ入り卵-1E1S; B.ジャンボソーセージ-0E5S。したがって、考えられる解は {A}.{B},{A,B} です。{A} の場合、4 つのソーセージが残ります。{B} の場合、卵が 1 つ残ります。{A,B} の場合、実際には違法または実行不可能なソリューションです。
私の質問は、残り物をどのように評価しますか? 鳥インフルエンザが発生している場合、卵は高値になる可能性があり、{B} が優先される可能性があります。したがって、各成分に価格を設定することで、いくつかのワイテッドサム関数を定義することができます。たとえば、fです。
加重和を使用する場合、これは多次元 KP と見なすことができます。品目はレシートであり、材料の数 1 (または長さと言う)、材料の数 2 (または幅と言う) などの複数の「メトリクス」があります...そして、たまたま多次元 (長さ) を持つバッグに詰められます。 、幅、...) したがって、実行可能なパッキングは、各次元の制約を満たさなければなりません。つまり、材料 k の合計使用量は、料理人が持つ材料 k の合計よりも少なくなければなりません。obj は、f (重量)、または最大f (使用される材料の量の価格) を最小化することです。インターネットの総価格、または単に最初の部分です。
私の知る限り、この問題は、次元数 (この場合は成分) が高くない限り解決可能です。これは切り株のようなものです。