Knapsack - APL-Exploration

https://isaac-flath.github.io/APL-Exploration/posts/knapsack.html

I wrote up one way to solve the knapsack problem. Again a basic computer science problem but you need some neat ideas to get a solution. I ended up using a lot more recursion than I was hoping for though :frowning: .

I am not sure how to vectorize it further. If anyone has ideas would love to hear them and try them out.

1 Like

Hi - I haven’t dissected the whole article yet, but I think it’s worth pointing out even a bruteforce solution can be reasonably performant.

For your example with 19 elements, a simple one line bruteforce {βŽ•io←0 β‹„ c w←↓⍉↑⍡ β‹„ m←2βŠ₯⍣¯1⍳2*n←≒⍡ β‹„ (n⍴2)βŠ€βŠƒβ’(c+.Γ—m)∧⍺β‰₯w+.Γ—m} is quicker than ks_solve.

      ]runtime -c 'ks_solve 19 31181 ,βŠ‚ items' '31181 bruteforce items'
                                                                                      
  ks_solve 19 31181 ,βŠ‚ items β†’ 2.0EΒ―1 |   0% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ• 
  31181 bruteforce items     β†’ 1.7EΒ―1 | -15% βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•βŽ•       

1 Like

Yep that works. Although I added two more examples 50 items and 1000 items.

Also the approach i used is susceptible to pathological datasets. You can craft an item list that is designed to trick the heuristics used. I’m going to play around with that some more.

You don’t seem to have included the 1000 item one.

Its up now.

@F73x how long does the 1000 element example take for you? It seems quite slow

It took a while.

Got a follow up on the previous post. Playing around with improving the performance.

(APL Exploration - Knapsack II)