3 ms·
This 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 pol
by arebop 17y ago
This 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).