3 ms·
Test HN: need a simple answer
This has me stumped - or rather annoyed :) A friend asked a simple question on a BB I frequent (dont worry, he's kosher and well out of school/uni age so it's not a "do my homework" query :D) regarding calculating monetary combinations.
Here is the brief summary in his words:
Probably not interesting to most people but I've again I've just underestimated an algorithm I thought would be very simple ...
I get paid a weekly total for many small daily jobs. All is well if I get paid for everything but if I don't then which jobs haven't I been paid for?
i.e. last week I was paid only paid £153.00 for the following list of [potential] jobs
£24.10,£45.40,£21.30,£7.55,£24.90,£24.50,£7.45,£1.25,£9.60,£30.00,£17.20,£21.05,£7.40,24.10,£9.35,£14.65,£4.25
Which payments am I missing?
My first answer was that there is approx. 130,000 (interesting anecdote: Wolfram Alpha was a bitch to get working on complex combinations, I did by hand in the end :D) combinations of the payments. So just compute, store in Sqlite/Mysql and then query for the total you get each week to retrieve the list of payments.
But I cant help feeling there must be a nicer way (i.e. one that means adding a new payment doest mean you need to reprocess). Maths is not my strongest focus.... so, HN, am I missing the obvious?
- arebop 17y agoThis is an instance of the subset-sum problem. It's NP-Complete. If there were a polynomial-time way to incrementally update the solution, then you'd have a polynomial-time way to solve any instance. So finding an easy way to solve this problem efficiently would be a major breakthrough for CS. Note for your application it probably doesn't matter whether you can solve the problem "efficiently" because it's feasible for you to check a hundred thousand possibilities. I'm just saying that you shouldn't expect to find a dramatic shortcut.
- ErrantX 17y agocheers. it was more an interesting mind experiment than trying to imporove on the obvious answer (it beign such a small set). The question being: can I build a system that works for both 17 jobs and 1000 with reasonable speed. Now I know why we ran against brick walls with the maths, thanks. (and actually a practical version of the NP-Complete issue helped me get my head round it better! many thanks).
- deleted 17y ago[deleted]
- ram1024 17y agoincomputable with the information given
- johnnybgoode 17y agoYou are right; there are 131,072 possibilities. Just have a computer go through them each week and see which ones match the weekly total. I'm sure there are nicer ways in terms of mathematical beauty, but if your friend is just trying to get work done, it doesn't really matter. Computers are fast.