ナップザックアルゴリズムの乗算

Question

私はNの数字をいくつか持っていますが、問題は、数字が以下のようなリストのすべての可能なセットを選択することです。コストの合計

例： - 数字のセットが

(number, costOfThatNumber) : {(90, 10) , (80, 20), (60, 40), (40, 60), (15, 85)}, 

で、製品がProd <= 1000、より小さくなければならない、

可能な解決策は以下のとおりです。 -

[Solution 1 :- {(15, 85), (40, 60)} :- Product = 600 (which is less than, 1000), cost = 85 + 60 = 145] 
[Solution 2 :- {(15, 85), (80, 20)} :- Product = 900 and cost = 105] 

ので、リストになり、 {Solution2, Solution1}。

PS： -

1. これは宿題の問題ではありません、それはインタビューで頼まれました。私はアルゴリズムだけを尋ねられました、私が言うことができるのは、ちょっとナップザックの問題と似ているが、乗算のためだと言える。
2. 問題を適切に説明できない場合は、申し訳ありません。

Answer 1

ナップザック問題の問題を軽減できると仮定します。

x1 * x2 * ... * xn <= M <-> 
log(x1*x2*...*xn) <= log(M) <-> 
log(x1) + log(x2) + ... + log(xn) <= log(M) 

だからナップザックを使用して最適解を見つける

注ことが行うことができます。

weight'(item) = log(weight(item)) 
value(item) = value(item) 
M' = log(M) 
run Knapsack on the items with weight', value, M' 

もっと仕事は、すべての実行可能な解決策を得るために必要な、最適なだけではなくなりますが、指数関数的に数値があるので（2^nならM = infinity）、疑似多項式の解が存在することは疑いの余地があります。

非効率的な解決策は、power set（すべての可能なセットを含むセット）を作成し、それらのそれぞれの実現可能性とその値をチェックし、それらの値に従って実行可能な解を順序付けられたセットに格納することです。 This postはパワーセットの取得方法を説明しています。

Answer 2

前述したように、これはナップザックの問題ではありません。ペアを昇順で並べ替え、最初から商品の制限に達するまで選択してから、コストに基づいて並べ替えます。前述したように、トータルコストがしきい値または限度を下回る必要はないので、最適な解決策は最初の要素が最小のペアを選択することです。