I have a list of products and a list of features. Each product has its own cost and delivers its own subset of the features.
I would like an algorithm such that I tell it which of the features I require and it will tell me the set of products I need to buy to get all of those features at the lowest total combined cost.
Does anyone have a recipe for doing something like that? I'd like to have it in JavaScript.
これが (加重)セット カバー問題です。力ずくで実行できないインスタンスを最適化する最も簡単で驚くほど効果的な方法は、整数プログラム ソルバーを実行することです。たとえば、Iain Dunning はSimplexJSと呼ばれるものを JavaScript で作成しました。(基本的な機能はあるように見えますが、飾り気のないもの (たとえば、プリソルバー、切断面、スパース線形代数) はありません。また、ライセンスやドキュメントの明らかな欠如は、あなたの好みに合わないかもしれません。代替品です。）
上記のウィキペディアのリンクは、セット カバーの抽象的な定式化を示しています。より具体的には、製品 A、B、C、D があり、関連する機能セットと価格が
A: {1, 2, 3}, 9.99
B: {2, 4}, 7.99
C: {3, 4}, 6.99
D: {4, 5}, 8.99 .
製品ごとに 1 つのバイナリ変数 xA、xB、xC、xD を作成します。変数 xA は、A を購入する場合は 1、購入しない場合は 0 です。私たちの目的は
minimize 9.99 xA + 7.99 xB + 6.99 xC + 8.99 xD .
すべての機能について、その機能を備えた製品を購入する必要があるという制約があります。
1: xA >= 1
2: xA + xB >= 1
3: xA + xC >= 1
4: xB + xC + xD >= 1
5: xD >= 1
適切なライブラリがあれば、インスタンスをこのようなプログラムに変換するコードを記述し、ソルバーを呼び出すだけです。
なんらかの理由で独自のライブラリを作成する必要がある場合は、分岐限定法と (デュアル)シンプレックス法について学習する必要があります。最適性を解決するための最良の検索戦略は、最適優先バックトラッキングを使用した深さ優先検索です。最終製品は、数百行のかなり複雑なコードになります。