title: Solving the NP-complete problem in XKCD
body: <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>