Solving the NP-complete problem in XKCD

Question

The problem/comic in question: http://xkcd.com/287/

I'm not sure this is the best way to do it, but here's what I've come up with so far. I'm using CFML, but it should be readable by anyone.

<cffunction name="testCombo" returntype="boolean">
    <cfargument name="currentCombo" type="string" required="true" />
    <cfargument name="currentTotal" type="numeric" required="true" />
    <cfargument name="apps" type="array" required="true" />

    <cfset var a = 0 />
    <cfset var found = false />

    <cfloop from="1" to="#arrayLen(arguments.apps)#" index="a">
        <cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) />
        <cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost />
        <cfif arguments.currentTotal eq 15.05>
            <!--- print current combo --->
            <cfoutput><strong>#arguments.currentCombo# = 15.05</strong></cfoutput><br />
            <cfreturn true />
        <cfelseif arguments.currentTotal gt 15.05>
            <cfoutput>#arguments.currentCombo# > 15.05 (aborting)</cfoutput><br />
            <cfreturn false />
        <cfelse>
            <!--- less than 15.05 --->
            <cfoutput>#arguments.currentCombo# < 15.05 (traversing)</cfoutput><br />
            <cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) />
        </cfif>
    </cfloop>
</cffunction>

<cfset mf = {name="Mixed Fruit", cost=2.15} />
<cfset ff = {name="French Fries", cost=2.75} />
<cfset ss = {name="side salad", cost=3.35} />
<cfset hw = {name="hot wings", cost=3.55} />
<cfset ms = {name="moz sticks", cost=4.20} />
<cfset sp = {name="sampler plate", cost=5.80} />
<cfset apps = [ mf, ff, ss, hw, ms, sp ] />

<cfloop from="1" to="6" index="b">
    <cfoutput>#testCombo(apps[b].name, apps[b].cost, apps)#</cfoutput>
</cfloop>

The above code tells me that the only combination that adds up to $15.05 is 7 orders of Mixed Fruit, and it takes 232 executions of my testCombo function to complete.

Is there a better algorithm to come to the correct solution? Did I come to the correct solution?

Solution 1

The point about an NP-complete problem is not that it's tricky on a small data set, but that the amount of work to solve it grows at a rate greater than polynomial, i.e. there is no O(n^x) algorithm.

If the time complexity is O(n!), as in (I believe) the two problems mentioned above, that is in NP.

Solution 2

It gives all the permutations of the solutions, but I think I'm beating everyone else for code size.

item(X) :- member(X,[215, 275, 335, 355, 420, 580]).
solution([X|Y], Z) :- item(X), plus(S, X, Z), Z >= 0, solution(Y, S).
solution([], 0).

Solution with swiprolog:

?- solution(X, 1505).

X = [215, 215, 215, 215, 215, 215, 215] ;

X = [215, 355, 355, 580] ;

X = [215, 355, 580, 355] ;

X = [215, 580, 355, 355] ;

X = [355, 215, 355, 580] ;

X = [355, 215, 580, 355] ;

X = [355, 355, 215, 580] ;

X = [355, 355, 580, 215] ;

X = [355, 580, 215, 355] ;

X = [355, 580, 355, 215] ;

X = [580, 215, 355, 355] ;

X = [580, 355, 215, 355] ;

X = [580, 355, 355, 215] ;

No

Solution 3

Isn't it more elegant with recursion (in Perl)?

#!/usr/bin/perl
use strict;
use warnings;

my @weights  = (2.15, 2.75, 3.35, 3.55, 4.20, 5.80);

my $total = 0;
my @order = ();

iterate($total, @order);

sub iterate
{
    my ($total, @order) = @_;
    foreach my $w (@weights)
    {
        if ($total+$w == 15.05)
        {
            print join (', ', (@order, $w)), "\n";
        }
        if ($total+$w < 15.05)
        {
            iterate($total+$w, (@order, $w));
        }
    }
}

Output

marco@unimatrix-01:~$ ./xkcd-knapsack.pl
2.15, 2.15, 2.15, 2.15, 2.15, 2.15, 2.15
2.15, 3.55, 3.55, 5.8
2.15, 3.55, 5.8, 3.55
2.15, 5.8, 3.55, 3.55
3.55, 2.15, 3.55, 5.8
3.55, 2.15, 5.8, 3.55
3.55, 3.55, 2.15, 5.8
3.55, 5.8, 2.15, 3.55
5.8, 2.15, 3.55, 3.55
5.8, 3.55, 2.15, 3.55

Solution 4

Even though knapsack is NP Complete, it is a very special problem: the usual dynamic program for it is in fact excellent (http://en.wikipedia.org/wiki/Knapsack_problem)

And if you do the correct analysis, it turns out that it is O(nW), n being the # of items, and W being the target number. The problem is when you have to DP over a large W, that's when we get the NP behaviour. But for the most part, knapsack is reasonably well behaved and you can solve really large instances of it with no problems. As far as NP complete problems go, knapsack is one of the easiest.

Solution 5

Here is the solution using constraint.py

>>> from constraint import *
>>> problem = Problem()
>>> menu = {'mixed-fruit': 2.15,
...  'french-fries': 2.75,
...  'side-salad': 3.35,
...  'hot-wings': 3.55,
...  'mozarella-sticks': 4.20,
...  'sampler-plate': 5.80}
>>> for appetizer in menu:
...    problem.addVariable( appetizer, [ menu[appetizer] * i for i in range( 8 )] )
>>> problem.addConstraint(ExactSumConstraint(15.05))
>>> problem.getSolutions()
[{'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 5.7999999999999998, 'mixed-fruit': 2.1499999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 7.0999999999999996},
 {'side-salad': 0.0, 'french-fries': 0.0, 'sampler-plate': 0.0, 'mixed-fruit':     15.049999999999999, 'mozarella-sticks': 0.0, 'hot-wings': 0.0}]

So the solution is to order a sampler plate, a mixed fruit, and 2 orders of hot wings, or order 7 mixed-fruits.

View more solutions

Comments

[Meff]

Beautiful. You'll probably get closed though as it's not a question :(

[vrbl]

You're missing 1 sampler, 2 hot wings, 1 mixed fruit.

[Adam Tuttle]

Whoops, accidentally left the question I intended to ask out. I've added it. Thanks!

[Paul Batum]

That language is an abomination. Its like VB and XML decided to have a baby.

[JavadocMD]

Eh, just solve it by brute force. :) I calculate an upper bound of about 1,715 combinations that should be examined.

[HenryR]

"Is there a better algorithm to come to the correct solution?" - this is one of the greatest unanswered question in computer science! If stackoverflow comes up with a general solution, I'll be very impressed :)

[yfeldblum]

The bastard child of two bastard childs. +1 Paul Batum.

[Admin]

Well you can tell just by looking at it that there's a better solution than brute force - the answer has to have an odd number of $?.?5 items to make the total end in .05. How you express that in code is a different matter...

[SPWorley]

But the problem in the comic isn't actually the knapsack problem. It's an integer programming problem. However it's also just looking for A solution, not the optimal combination, so I don't know if it's really NP since it's not actually knapsack or full IP.

[Noldorin]

@Paul Batum: That gave me a good laugh. My sentiments precisely.

[Peter C]

There's a language that actually looks like that? *vomits*

[Meff]

Mixed Fruit,hot wings,hot wings = 15.05? 2.15 + 3.55 + 3.55 = 9.25

[vrbl]

As I mentioned in my answer, he's not printing the last element in each of the combos.

[Adam Tuttle]

I'm not sure why you can delete the item from the array. Seems to me that in this case it's ok, but wouldn't necessarily be true for all cases. Can you explain that a bit more?

[Sklivvz]

It's a different problem, the knapsack problem assumes non exact solutions, and a choice without duplicates.

[Adam Tuttle]

Ok, I see how removing elements is helpful now. Looks like you're (effectively) passing by val, & not by ref. Is that true? I've been passing by ref to preserve memory and keep run time down, but the trade-off of fewer recursions may give the win to by value w/ deletes. (I'll time it to see.)

[vrbl]

Yes, you're right, it's essentially passing by value (I was lazy). You can improve on that by passing a minimum index to check to the recursive function rather than the modified arrays.

[Windows programmer]

Then why did the restaurant patron offer the waiter articles on the knapsack problem?

[Jasper Bekkers]

Probably because its a cartoon.

[FryGuy]

This particular version also simplifies to O(n * lcm(numbers)). If your sacks are fairly good, then that might be less than W.

[josesuero]

Because the problems are closely related. Solving the knapsack problem will solve this one too.

[Mark Allanson]

You need to add a sort in there after calculating an answer so you can strip dupes.

[elcuco]

Fix it to display the actualy orders (not the values!) and you get voted up!