用于乘法的背包算法

Question

我有一组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. 如果我无法正确解释问题,请原谅.

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^nif M = infinity),我怀疑甚至存在伪多项式解.

一种非有效的解决方案就是创建功率集(包含所有可能的集合的集合),并检查它们的可行性和价值,并根据它们的值在有序集合中存储可行的解决方案.这篇文章解释了如何获得电源.