Databases
StackOverflow2013
Postsdbo
POSolving the NP-complete problem in XKCD
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSolving the NP-complete problem in XKCD
    text
    copied!<p>The problem/comic in question: <a href="http://xkcd.com/287/" rel="nofollow noreferrer">http://xkcd.com/287/</a></p> <p><img src="https://imgs.xkcd.com/comics/np_complete.png" alt="General solutions get you a 50% tip"></p> <p>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.</p> <pre><code>&lt;cffunction name="testCombo" returntype="boolean"&gt; &lt;cfargument name="currentCombo" type="string" required="true" /&gt; &lt;cfargument name="currentTotal" type="numeric" required="true" /&gt; &lt;cfargument name="apps" type="array" required="true" /&gt; &lt;cfset var a = 0 /&gt; &lt;cfset var found = false /&gt; &lt;cfloop from="1" to="#arrayLen(arguments.apps)#" index="a"&gt; &lt;cfset arguments.currentCombo = listAppend(arguments.currentCombo, arguments.apps[a].name) /&gt; &lt;cfset arguments.currentTotal = arguments.currentTotal + arguments.apps[a].cost /&gt; &lt;cfif arguments.currentTotal eq 15.05&gt; &lt;!--- print current combo ---&gt; &lt;cfoutput&gt;&lt;strong&gt;#arguments.currentCombo# = 15.05&lt;/strong&gt;&lt;/cfoutput&gt;&lt;br /&gt; &lt;cfreturn true /&gt; &lt;cfelseif arguments.currentTotal gt 15.05&gt; &lt;cfoutput&gt;#arguments.currentCombo# &gt; 15.05 (aborting)&lt;/cfoutput&gt;&lt;br /&gt; &lt;cfreturn false /&gt; &lt;cfelse&gt; &lt;!--- less than 15.05 ---&gt; &lt;cfoutput&gt;#arguments.currentCombo# &lt; 15.05 (traversing)&lt;/cfoutput&gt;&lt;br /&gt; &lt;cfset found = testCombo(arguments.currentCombo, arguments.currentTotal, arguments.apps) /&gt; &lt;/cfif&gt; &lt;/cfloop&gt; &lt;/cffunction&gt; &lt;cfset mf = {name="Mixed Fruit", cost=2.15} /&gt; &lt;cfset ff = {name="French Fries", cost=2.75} /&gt; &lt;cfset ss = {name="side salad", cost=3.35} /&gt; &lt;cfset hw = {name="hot wings", cost=3.55} /&gt; &lt;cfset ms = {name="moz sticks", cost=4.20} /&gt; &lt;cfset sp = {name="sampler plate", cost=5.80} /&gt; &lt;cfset apps = [ mf, ff, ss, hw, ms, sp ] /&gt; &lt;cfloop from="1" to="6" index="b"&gt; &lt;cfoutput&gt;#testCombo(apps[b].name, apps[b].cost, apps)#&lt;/cfoutput&gt; &lt;/cfloop&gt; </code></pre> <p>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.</p> <p>Is there a better algorithm to come to the correct solution? Did I come to the correct solution?</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload