There's a neat Haskell solution to the knapsack problem which runs very fast.  I'm not 100% sure that it runs faster than an optimal solution in other GC'd imperative languages, but it's very concise and not (too) convoluted.  Have a search for the thread with "xkcd" in the title.
<br><br>Chung-chieh Shan wrote:<br>&nbsp;&nbsp; &nbsp;<br>Here&#39;s my solution to the xkcd problem (yay infinite lists):<br><br>xkcd_c287&#39; = foldr<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (\cost without -&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let (poor, rich) = splitAt cost without
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; with = poor ++ zipWith (++) rich (map (map (cost:)) with)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; in with)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ([[]] : repeat [])<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; !!<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1505 -- 150005
<br><br>Replacing the two lines with comments by the comments solves your case<br>quickly.<br><br>Explication of how it works from &quot;<a href="mailto:haskell@list.mightyreason.com">haskell@list.mightyreason.com</a>&quot;:
<br><br>I will jump in and explain, using a more finely named version:<br><br>xkcd_c287&#39; = foldr<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (\cost without -&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let (poor, rich) = splitAt cost without<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; with = poor ++ zipWith (++) rich using_cost
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; using cost = (map (add_cost) with)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; where add_cost xs = cost:xs<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; in with)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ([[]] : repeat [])<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [215, 275, 335, 355, 420, 580] -- [2, 4, 150001]<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; !!<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1505 -- 150005<br><br>At the top level it uses (!!) to pick the 1505th element of the list produced by<br>the use of foldr.<br><br>foldr &lt;function to combine new value with previous result&gt;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;seed result&gt;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &lt;list of new values&gt;<br><br>Here the list of new values is the list of item prices (in pennies) from the menu.<br><br>The seed result is the answer in the absence of anything on the menu.
<br><br>The seed is ([[]] : repeat []) which is a list of (list of prices).&nbsp; The &quot;n th&quot;<br>member of the outer list holds the solution for a price of &quot;n pennies&quot;.<br><br>Thus the (!! 1505) selects the answer for a target price of $15.05.
<br><br>The seed result has an empty list in the 0th position since ordering nothing is<br>a solution to a target price of $0.00.<br><br>The function works as follows:<br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (\cost without -&gt;<br><br>The &#39;cost&#39; is the price of the new item on the menu.
<br>The &#39;without&#39; is the answer taking into account all previously processed items<br>on the menu (before the &#39;cost&#39; item).<br>The result will be a new answer taking into account &#39;cost&#39; as well.<br>
<br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; let (poor, rich) = splitAt cost without<br><br>The items in the old answer &#39;without&#39; before the index &#39;cost&#39; are solutions for<br>a target price cheaper than &#39;cost&#39; and these are in the &#39;poor&#39; list.&nbsp; These
<br>answers are unchanged by the addition of the &#39;cost&#39; item.<br><br>The items in the &#39;rich&#39; part of the answer may get new solutions that include<br>ordering the new &#39;cost&#39; item.<br><br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; with = poor ++ zipWith (++) rich using_cost
<br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; using cost = (map add_cost with)<br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; where add_cost xs = cost:xs<br>&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; in with)<br><br>The new answer will be &#39;with&#39; which is defined recursively.<br><br>
The first elements of &#39;with&#39; are the &#39;poor&#39; parts of the old answer &#39;without&#39;<br>that are obviously unchanged.<br><br>The &#39;zipWith (++) rich using_cost&#39; combines the previous &#39;rich&#39; answers without
<br>&#39;cost&#39; with a new list that uses the &#39;cost&#39; item.&nbsp; This is:<br><br>using cost = (map add_cost with)<br>&nbsp; where add_cost xs = cost:xs<br><br>The using_cost list is made from taking the list of answers and prepending the
<br>&#39;cost&#39; item to all the solutions.<br><br>If this were applied to &#39;without&#39; instead of &#39;with&#39;...<br><br>using cost = (map add_cost without)<br>&nbsp; where add_cost xs = cost:xs<br><br>...then the definition of &#39;with&#39; would not be recursive and would allow for
<br>solutions that only order each menu item 0 or 1 times.<br><br>Since the definition of using_cost does apply the map to &#39;with&#39; it can add_cost<br>to answers that already have has add_cost applied to them.&nbsp; Thus it finds all
<br>answers that order the menu items 0,1,2,3.. arbitrarily many times.<br><br>The &quot;n th&quot; item in &#39;with&#39; or &#39;without&#39; has total price of &quot;n&quot;, and after<br>add_cost it has a total price of &quot;cost+n&quot;, and must be in the &quot;(cost+n)th&quot;
<br>position in the answer &#39;with&#39;.&nbsp; This is achieve by the using_cost items being<br>after the (poor ++) which means they have been shifted by (length poor)<br>positions which, by the definition of (splitN cost), is equal to &#39;cost&#39;.
<br><br><br>