相关疑难解决方法(0)

解决XKCD中的NP完全问题

问题/漫画有问题:http://xkcd.com/287/

一般解决方案可为您提供50%的小费

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

<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 /> …
Run Code Online (Sandbox Code Playgroud)

language-agnostic np-complete

45
推荐指数
4
解决办法
1万
查看次数

标签 统计

language-agnostic ×1

np-complete ×1