所涉及的问题/漫画: http://xkcd.com/287/
我不确定这是否是最好的方法,但这是我目前想出来的。我正在使用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 />
<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次。
是否有更好的算法可以得出正确的解决方案?我是否已经得出了正确的解决方案?