looping through possible combinations of McNuggets packs of 6, 9 and 20

Baba raoulbia at gmail.com
Tue Aug 17 23:44:22 CEST 2010


On Aug 16, 6:28 pm, "cbr... at cbrownsystems.com"
<cbr... at cbrownsystems.com> wrote:

> First, suppose d = gcd(x, y, z); then for some x', y', z' we have that
> x = d*x', y = d*y', z = d*z'; and so for any a, b, c:
>


   could you explain the notation?

   what is the difference btw x and x' ?

   what is x = d*x', y supposed to say?



> To go the other way, if d = 1, then there exists integers (not
> neccessarily positive) such that
>
> a*x + b*y + c*z = 1
>


   what's the link with 6*a+9*b+20*c=n except the similarity?



furthermore i came across this:

For k = 3, efficient algorithms
have been given by Greenberg and Davison ; if x1 < x2 < x3, these
algorithms run in
time bounded by a polynomial in log x3. Kannan  gave a very
complicated algorithm
that runs in polynomial time in log xk if k is fixed, but is wildly
exponential in k. However,
Ram´ırez Alfons´ın proved that the general problem is NP-hard, under
Turing reductions,
by reducing from the integer knapsack problem. So it seems very likely
that there is no
simple formula for computing g(x1, x2, . . . , xk) for arbitrary k.

source: http://arxiv.org/PS_cache/arxiv/pdf/0708/0708.3224v1.pdf


i would be interested in the answer to problem 3: explain in English
why the theorem is true

@Giacomo: when you say that i have not read the text of the assignment
i tend to disagree. Therefore could you point out what it is i
overlooked that should help me prove my assumption for the
generalisation? Enjoy the sausages btw :)

tnx
Baba









More information about the Python-list mailing list