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 .
I am not sure how to vectorize it further. If anyone has ideas would love to hear them and try them out.
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.
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.