1

ここで問題：

それぞれの量を含む成分のリスト (値が単一であると仮定) と、製品のリストを取得します。各製品には、必要な材料とその量を含む価格とレシピが含まれています。

必要なのは、指定された成分を含む製品からの総収益を最大化することです。

最初に思いついたのは、価格/(必要なアイテム数) の比率を作成し、比率が最も高い製品の作成を開始することです。これはある種の貪欲なアルゴリズム (私が間違っていなければ) であり、常に最良の解決策につながるとは限らないことはわかっていますが、他に実装可能なアイデアはありませんでした。

別の方法は、すべての可能性を総当たりにすることかもしれませんが、それを実装する方法を理解できません。私は総当たり攻撃にあまり慣れていません。私の最初の強引なアルゴリズムはこれでしたが、数字なので簡単でした。さらに、後に続く要素は前の要素によって排除されません。

次の要素は、以前の製品から影響を受けた利用可能な成分の関数であるため、ここでは事情が異なります。

ヒントはありますか？これは一種の宿題なので、直接的な解決策ではなく、何かから始めることを好みます。

私が使わなければならない言語はCです

よろしくお願いします:)

4

2 に答える 2

5

私はまず、これを線形計画問題として見てみます。それらを効率的に解決するために利用できるアルゴリズムがあります。

問題が小数の項目を受け入れることができない場合、それは実際には整数計画問題です。これらを解決するために利用できるアルゴリズムもありますが、一般に、大きな整数計画問題を正確に解決するのは (時間がかかるため) 難しい場合があります。

線形計画法の解は、たとえば生産量が多い場合、整数計画法の解に対する適切な最初の近似である可能性があることに注意してください。

于 2013-05-10T16:28:33.293 に答える
3

それを行うための CPU サイクルがある場合 (そして効率は問題ではありません)、ブルート フォースはおそらく最良の方法です。

おそらく最初にすべきことは、選択肢を列挙する方法を見つけることです。つまり、与えられた材料で作ることができるペストリーのさまざまな組み合わせをすべてリストする方法を考え出すことです. 最初は価格を気にする必要はありません。

(不自然な) 例として、牛乳 1 杯と卵 12 個と小麦粉と砂糖を使って、次のように作ることができます。

  • ブラウニー12個
  • ブラウニー11個とクッキー1個
  • ブラウニー10個とクッキー2個
  • [...]
  • ブラウニー1個とクッキー11個
  • 12個のクッキー

次に、そのリストを取得したら、リストを繰り返し処理し、各オプションでどれだけのお金を稼ぐかを計算し、最も多くのお金を稼ぐものを選択します.

オプションのリストを生成する限り、Cookie のみを作成する場合に作成できる Cookie の数を計算することから始めます。次に、ブラウニーだけを作るとしたら、いくつのブラウニーを作ることができるか、などです。これにより、考慮する必要がある各アイテムの数の絶対的な上限が得られます。次に、タイプごとの数がその境界以下のアイテムのすべての組み合わせを検討し、手元にあるよりも多くの材料を必要とすることが判明した組み合わせを捨てることができます. もちろん、これは非常に非効率的で遅くなりますが、機能します。

于 2013-05-10T16:19:32.323 に答える