CODEWITHSUNDEEP
algorithmknapsack-problem
user1045047
user1045047

Reputation: 379

Knapsack algorithm for multiplication

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 :-

  1. 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.
  2. Please excuse if i am unable to explain the problem properly.

Upvotes: 0

Views: 1155

Answers (2)

Antti Huima
Antti Huima

Reputation: 25532

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.

Upvotes: 0

amit
amit

Reputation: 178471

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.

Upvotes: 5

Related Questions