Re:The Knapsack Problem Is All Around Us
by mjevans on Monday March 09, 2020 @10:47PM
(#22532313)
I imagine that MOST excel sheets are small enough for some variation of brute force to work. Lots of times a very rough approximation is a good enough place to start.
[ Parent
| on HN ]
Reminds me a bit of when my dad asked me what was a good sort algorithm to use for his problem. When he asked I was mentally trying to weigh complexity to implement vs performance (he was a firmware programmer, it had to be in assembly).
Then I remembered to ask: how many things are you going to sort? He said 10. Always 10.
So, yeah. I didn't really even know the answer at the time.
I had to check 10! just to see how bad this could be. At 10 it's 3,628,800. Depending on how beefy the system is and how costly the operation is, pure brute force but simple might be good enough.
A nice solution that is easy to implement in Excel is using a sorting network, that sorts an array by doing the same exchanges for any input. Here I did it just for fun: https://imgur.com/a/qPugrJ6
wow that's pretty.
Re:The Knapsack Problem Is All Around Us
by owenshen24 on Tuesday March 10, 2020 @12:58AM
(#22532856)
I think you could get by with ~50 checks if you just used selection sort.
I'm not sure what brute-forcing means in this context. Do you mean hard-coding every way to order 10 unique elements?
Brute force sorting would be generating permutations and checking if they're sorted. The non-deterministic version that uses random permutations is commonly called bogosort[0]
The thread switched problems and I didn't catch that. The 10 factorial was trying out all possible packing solutions and filtering for only the ones that were 'valid' (probably with an added step of also keeping the best valid configuration).