解决XKCD中的NP完全问题 [英] Solving the NP-complete problem in XKCD

问题描述

相关问题/漫画: http://xkcd.com/287/

我不确定这是最好的方法，但是到目前为止，这是我要提出的.我正在使用CFML，但任何人都应该可以读取.

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>

上面的代码告诉我，唯一加起来为$ 15.05的组合是7个混合水果订单，并且需要232次testCombo函数的执行才能完成.

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?

推荐答案

关于NP完全问题的要点不是在小数据集上棘手，而是解决问题的工作量以更大的速度增长比多项式，即没有O(n ^ x)算法.

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.

如果时间复杂度为O(n！)，如(我相信)上述两个问题，那就是NP.

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

这篇关于解决XKCD中的NP完全问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！