Knapsack algorithm for multiplication

Question

I have a set of N numbers with some cost attached to each number, and the problem is to choose all possible set of numbers as a list such that their product is less than a certain number M, sorted according to the sum of cost.

Eg :- The set of numbers is

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

and the Product must be less than, Prod <= 1000,

Possible solutions are :-

[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]

So the list becomes, {Solution2, Solution1}.

PS :-

This is not a homework problem, it was asked in an interview. I was asked only the algorithm, all i could say was that it looks kinda similar to knapsack problem, but for multiplication.
Please excuse if i am unable to explain the problem properly.

If not the optimal solution, i would appreciate even if someone gives me a brute force algorithm, i could even find a way to select all possible subsets of the sets. — user1045047, May 10 '12 at 18:13
Is your example wrong? 15*80 is not 900... Shouldn't that be (15, 85),(60,40)? — svinja, May 11 '12 at 06:56

score 5 · Answer 1 · edited May 23 '17 at 10:09

I assume one can reduce the problem to the knapsack problem.

Note that

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

So finding the optimal solution using the knapsack can be done:

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

More work will be needed to get all feasible solutions, and not only the optimal, but since there are exponential number of those (2^n if M = infinity), I doubt there is even pseudo-polynomial solution for this.

A non efficient solution is just creating the power set (A set containing all possible sets), and checking each of them for feasibility and its value, and storing in ordered set the feasible solutions, according to their value. This post explains how to get the power set.

This is one of the few cases where the optimal algorithm is certainly of exponential running time (to get all solutions), simply because worst case output size is exponential. Output size is a lower bound for complexity in all cases. If you need to calculate and fill X locations in memory you need X steps to do it, there is no way around it, despite of how trivially each result may be calculated. — svinja, May 11 '12 at 07:19

score 0 · Answer 2 · answered May 11 '12 at 06:22

As stated, it's not Knapsack problem. Just sort the pairs in increasing order, pick from the beginning until the product limit is reached, and then re-sort based on cost. As stated, there is no requirement that the total cost should be below any threshold or limit, so the optimal solution is just to pick the pairs with smallest first elements.

Knapsack algorithm for multiplication

2 Answers2