0

各数値にいくつかのコストが付加された数値のセットがNあり、問題は、可能なすべての数値のセットをリストとして選択して、それらの積が特定の数値未満になりM、コストの合計に従ってソートされることです。

例:- 数値のセットは

(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. 問題を適切に説明できない場合は、ご容赦ください。
4

2 に答える 2

5

問題をナップザック問題に還元できると思います。

ご了承ください

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^nif M = infinity)、これには疑似多項式解さえあるとは思えません。

非効率的な解決策は、べき乗セット(すべての可能なセットを含むセット) を作成し、それぞれの実現可能性とその値をチェックし、その値に従って実行可能なソリューションを順序付けられたセットに格納することです。この投稿では、パワー セットを取得する方法について説明します。

于 2012-05-10T18:28:50.743 に答える
0

述べたように、それはナップサック問題ではありません。ペアを昇順で並べ替え、最初から製品の制限に達するまで選択してから、コストに基づいて並べ替えるだけです。前述のように、総コストがしきい値または制限を下回る必要はないため、最適なソリューションは、最初の要素が最小のペアを選択することです。

于 2012-05-11T06:22:52.973 に答える