language agnostic - Solving the NP-complete problem in XKCD -

-

the problem/comic in question: http://xkcd.com/287/

general solutions 50% tip

i'm not sure best way it, here's i've come far. i'm using cfml, should readable 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 = 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 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>

the above code tells me combination adds $15.05 7 orders of mixed fruit, , takes 232 executions of testcombo function complete.

is there better algorithm come correct solution? did come correct solution?

the point np-complete problem not it's tricky on small data set, amount of work solve grows @ rate greater polynomial, i.e. there no o(n^x) algorithm.

if time complexity o(n!), in (i believe) 2 problems mentioned above, in np.


Comments

Post a Comment

Popular posts from this blog

c++ - How do I get a multi line tooltip in MFC -

-
right now, have tool tip pops when hover on edit box. problem tool tip contains multiple error messages , in 1 long line. need have each error message on own line. error messages contained in cstring new line seperating them. my existing code below. bool ontooltiptext(uint, nmhdr* pnmhdr, lresult* presult) { assert(pnmhdr->code == ttn_needtexta || pnmhdr->code == ttn_needtextw); // need handle both ansi , unicode versions of message tooltiptexta* pttta = (tooltiptexta*)pnmhdr; tooltiptextw* ptttw = (tooltiptextw*)pnmhdr; // tchar szfulltext[256]; cstring strtiptext=_t(""); uint nid = pnmhdr->idfrom; if (pnmhdr->code == ttn_needtexta && (pttta->uflags & ttf_idishwnd) || pnmhdr->code == ttn_needtextw && (ptttw->uflags & ttf_idishwnd)) { // idfrom hwnd of tool nid = ::getdlgctrlid((hwnd)nid); } //m_errprojaccel[ch] contains 1 or more error messages each...
Read more

asp.net - In javascript how to find the height and width -

-
i having .aspx , masterpage page. in masterpage loading aspx page . in aspx page design using generating table structure using code-behind server in javascript how find height , width . regards, kumar if you're looking table height , width, should it var tbl = document.getelementbyid('tbldemo'); alert(tbl.offsetwidth + '\n' + tbl.offsetheight);
Read more

c# - DataTable to EnumerableRowCollection -

-
i have datatable according client requirement can contain invalid date "00/00/1999",null,empty string.(typed datset) when collect them enumerables wish convert of invalid forms empty string. (i.e) enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || (how check date invalid date) ? string.empty : order.field<datetime>("orderdate") } how check whether date valid date or not? datetime.tryparse...like given current code: datetime date; enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || !datetime.tryparse(convert.tostring(order.field<datetime...
Read more