News for hackers. Stuff that matters.
Re:The Knapsack Problem Is All Around Us by klenwell on Monday March 09, 2020 @10:09PM (#22532120)
First time I encountered this in the wild was years ago when my sister, who worked as auditor, approached me with a problem she hoped I could help her solve. She would often be given a spreadsheet full of values and she would have a target or aggregate value she was trying to match. Could I write a script to find the set of values from the spreadsheet that would add up to her target value?

Piece of cake I thought. After a couple hours of fruitless coding I realized some research might help. After a few more hours of googling, I finally figured out the name for this type of problem. Actually, I first came across the term "subset sum problem" which led to "knapsack problem". That led to an introduction to the concept of "nondeterministic polynomial time".

Eventually I found a diophantine algorithm someone had written in Rexx and managed to translate it to Python. It worked! Sorta. (I was surprised by how many different matching combinations a random set of numbers could generate for a given value.)

By the time I returned to my sister with my solution, I think she had found a Excel plugin that did it for her.

Re:The Knapsack Problem Is All Around Us by andreareina on Tuesday March 10, 2020 @12:06AM (#22532639)
Subset sum is something that comes up quite often when bookkeepers need to reconcile accounts and there's some transactions missing. And indeed, the Excel solvers work well enough. These days I'm no longer surprised to find out that a classic selection problem has an Excel plug-in to solve it. There's even one for the multiple knapsack apparently.
Re:The Knapsack Problem Is All Around Us by larrydag on Tuesday March 10, 2020 @09:12AM (#22535116)
You can create a solution for the knapsack problem using Excel Solver.
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.
Re:The Knapsack Problem Is All Around Us by bcrosby95 on Monday March 09, 2020 @11:56PM (#22532605)
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.

Re:The Knapsack Problem Is All Around Us by mjevans on Tuesday March 10, 2020 @12:27AM (#22532724)
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.
Re:The Knapsack Problem Is All Around Us by rbonvall on Tuesday March 10, 2020 @08:49AM (#22534940)
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
Re:The Knapsack Problem Is All Around Us by istinetz on Tuesday March 10, 2020 @11:41AM (#22536382)
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?

Re:The Knapsack Problem Is All Around Us by the8472 on Tuesday March 10, 2020 @01:58AM (#22533134)
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]

[0] https://en.wikipedia.org/wiki/Bogosort

Re:The Knapsack Problem Is All Around Us by mjevans on Tuesday March 10, 2020 @03:13PM (#22538561)
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).
Re:The Knapsack Problem Is All Around Us by easymovet on Tuesday March 10, 2020 @09:41AM (#22535338)
I built the same thing for a logistics company, went down the same learning route too!