Re: knapsack related question


JoJo wrote:
> Hi all,
>
> I have the following question: suppose I have a set
> S of primes p (each prime can be present multiple
> times in the set), and I have a number X. If the
> product of all the primes in S is larger than X,
> then I should be able to select a subset T from S,
> such that the product of primes in T approaches the
> value X best.
>
> If we take the log of all values, then the problem
> is converted to the summation of a subset of values,
> this can be seen as the knapsack problem with binary
> weights applied to log(S) (I guess, I'm certainly
> not an expert here...).

You almost got there. 8-) "Binary weights" means that each prime could
only be included once. What you want are integer weights. (You may be
able to get a binary weight problem out of it by listing log(p) more
than once.)

> The problem now is: is there an algorithm that solves
> this problem (the original product-problem or the
> knapsack problem), described in such a way that it
> can be implemented in software? I did some searches
> on the Internet and could not find a good entry which
> helps me further to a good solution.

Being a knapsack problem, I doubt that there are any *short*
algorithms.

One paper that lists a couple of algorithms is:

Hifi, Mhand; Sadfi, Slim; Sbihi, Abdelkader. An efficient algorithm for
the knapsack sharing problem. Comput. Optim. Appl. 23 (2002), no. 1,
27--45.

(I got this paper by going to http://ams.rice.edu/mathscinet/search/
and searching for knapsack and algorithm*. If you have access, this
would be a recommended place to go. Approximat* would also be a good
search term, to approximate.)

One thing you didn't mention was whether there was anything special
about the primes or about X. If so, maybe that can be exploited.

--- Christopher Heckman

.

Relevant Pages

  • Re: Math errors in book Secret Life of Numbers
    ... his students have proven that primes can be found in polynomial time. ... For practical purposes the algorithm is, admittedly, still too ... that in practice, it always was solved in polynomial time using the ... the simplex method is not a polynomial-time algorithm. ...
    (sci.math.research)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
  • Re: Prime Number Question
    ... were discovered a simply algorithm for generating all prime numbers ... directly, in batches, with each batch being used ... the current best factoring method, the number field sieve, only becomes ... characteristic of primes ...
    (comp.unix.bsd.openbsd.misc)
Quantcast