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^n如果M = infinity），我怀疑甚至有伪多项式解决方案。

一个非有效的解决方案只是创建幂集（包含所有可能集的集合），并检查它们中的每一个的可行性及其值，并根据它们的值将可行的解决方案存储在有序集中。这篇文章解释了如何获得电源组。

于 2012-05-10T18:28:50.743 回答
0

如前所述，这不是背包问题。只需按升序排序，从头开始挑选直到达到产品限制，然后根据成本重新排序。如前所述，不要求总成本应低于任何阈值或限制，因此最佳解决方案只是选择具有最小第一个元素的对。

于 2012-05-11T06:22:52.973 回答