title: Haskell Knapsack
body: <p>I've written an answer to the bounded knapsack problem with one of each item in Scala, and tried transposing it to Haskell with the following result:</p>
  
  <pre><code>knapsack :: [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ] -&gt; Int -&gt; [ ( Int, Int ) ]
  knapsack xs [] _   = xs
  knapsack xs ys max =
      foldr (maxOf) [ ] [ knapsack ( y : xs ) ( filter (y /=) ys ) max | y &lt;- ys
          , weightOf( y : xs ) &lt;= max ]
  
  maxOf :: [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ]
  maxOf a b = if valueOf a &gt; valueOf b then a else b
  
  valueOf :: [ ( Int, Int ) ] -&gt; Int
  valueOf [ ]        = 0
  valueOf ( x : xs ) = fst x + valueOf xs
  
  weightOf :: [ ( Int, Int ) ] -&gt; Int
  weightOf [ ]        = 0
  weightOf ( x : xs ) = snd x + weightOf xs
  </code></pre>
  
  <p>I'm not looking for tips on how to clean up the code, just to get it working. To my knowledge it should be doing the following:</p>
  
  <ul>
  <li>For each tuple option (in ys)
  <ul>
  <li>if the weight of the current tuple (y) and the running total (xs) combined is less than the capacity</li>
  <li>get the optimal knapsack that contains the current tuple and the current total (xs), using the available tuples (in ys) less the current tuple</li>
  </ul></li>
  <li>Finally, get the most valuable of these results and return it</li>
  </ul>
  
  <p>*<em>Edit: *</em> Sorry, forgot to say what's wrong... So it compiles alright, but it gives the wrong answer. For the following inputs, what I expect and what it produces:</p>
  
  <pre><code>knapsack [] [(1,1),(2,2)] 5
  Expect: [(1,1),(2,2)]
  Produces: [(1,1),(2,2)]
  
  knapsack [] [(1,1),(2,2),(3,3)] 5
  Expect: [(2,2),(3,3)]
  Produces: []
  
  knapsack [] [(2,1),(3,2),(4,3),(6,4)] 5
  Expect: [(2,1),(6,4)]
  Produces: []
  </code></pre>
  
  <p>So I was wondering what could be the cause of the discrepancy?</p>
  
  <p>The solution, thanks to sepp2k:</p>
  
  <pre><code>ks = knapsack []
  
  knapsack :: [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ] -&gt; Int -&gt; [ ( Int, Int ) ]
  knapsack xs [] _   = xs
  knapsack xs ys max =
      foldr (maxOf) [ ] ( xs : [ knapsack ( y : xs ) ( ys #- y ) max
                               | y &lt;- ys, weightOf( y : xs ) &lt;= max ] )
  
  (#-) :: [ ( Int, Int ) ] -&gt; ( Int, Int ) -&gt; [ ( Int, Int ) ]
  [ ]        #- _ = [ ]
  ( x : xs ) #- y = if x == y then xs else x : ( xs #- y )
  
  maxOf :: [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ] -&gt; [ ( Int, Int ) ]
  maxOf a b = if valueOf a &gt; valueOf b then a else b
  
  valueOf :: [ ( Int, Int ) ] -&gt; Int
  valueOf [ ]        = 0
  valueOf ( x : xs ) = fst x + valueOf xs
  
  weightOf :: [ ( Int, Int ) ] -&gt; Int
  weightOf [ ]        = 0
  weightOf ( x : xs ) = snd x + weightOf xs
  </code></pre>
  
  <p>Which returns the expected results, above.</p>