algorithm - Getting the biggest subset under a certain limit? -
given list of reals a = [a1, a2, a3,..., an] , real x, there polynomial-time algorithm gets subset b of a such that:
sum(b) <= x; , there not exist subset c of a such sum(c) <= x , sum(b) < sum(c)?
i'm 99% sure can't done. sounds restatement of knapsack problem -- or, @ least, knapsack problem can reduced this. unless p=np, you're out of luck.
algorithm language-agnostic complexity-theory time-complexity
No comments:
Post a Comment