3 ms·
Might get you close: Until you have 1000 Find the package not included that adds the most deps If it adds less than everything you have
by travisjungroth 6y ago
Might get you close:
Until you have 1000
Find the package not included that adds the most deps
If it adds less than everything you have
Add it
Else
Kick out anything that adds less than that
And then make that a package and repeat as desired.
- OskarS 6y agoYeah, that's the greedy algorithm and it will probably take you pretty far, but there's no guarantee that it's optimal. What if the package has lots of dependencies, but they are already covered by other packages. Do you kick other packages out? Which ones? Or is it better to keep them in and add some other packages? This problem is almost certainly NP-complete (it's basically the the "set cover" problem from Karp's 21 NP-complete problems), so for something the size of NPM it's almost certainly infeasible. Your greedy version would probably get you a pretty nice result, though.
- travisjungroth 6y agoI don't think it's optimal, but I tried to account for some of what you're saying. I'd take in whatever adds the most new dependencies if the amount it would add is lower or equal to the least contributing package I have. Otherwise, kick stuff out and recalculate.