On Sun, 14 Nov 2004 02:48:14 +0900
"Florian G. Pflug" <fgp / phlo.org> wrote:

> Hi
>
> I just starten thinking about an algorithm to solve this - and I
> stumbled upon the following:
>
> The "Countdown"-Quiz kind of a generalization of a Knapsack-Problem,
> isn't it? If I recall correctly, solving a Knapsack means to find
> a way to construct a given number by chosing which numbers (from a given
>    set) to _sum_ up - or did I mix this up with something else?
>
> If a further recall correctly that solving a general Knapsack is
> NP-hard, the Countdown-Quit is NP-hard too, isn't it?
>
> I'd appreciate any comment on this.
>
> Greetings, Florian Pflug
>

Knapsack is a maximization problem.

You have objects o_i = (v_i, w_i) with a value v_i and a weight w_i.

Your Knapsack is limited to a total weight of 1.0.

Now choose a subset S of the objects, such that \sum_{o_i\in S} v_i is maximized.

It is true that this is np-hard.

Countdown is no direct superset of knapsack, but I'm shure its reductible on it.

It is possible to approximate knapsack (see scaled knapsack). But in this case we have a fixed and low number of cards, so it is possible to simply take on the combinatorial explosion and enumerate every solution.

One could also try to find an approximate solution, but those will be harder for JEGII to test automatically ;)

The simplest implementation that uses only constant memory takes around three minutes for six cards on my machine.

A more memory intensive version can do this in about half to third of the time.

Regards,

Brian

--
Brian Schröäer
http://www.brian-schroeder.de/