Maximum subset of set of Integers with minimum distance

Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for my example ({0,1,3,100,102}) and the distance 3 the result could be: {0,3,100} for distance 2 it could be: {0,3,100,102}

Is there an "good" algorithm to do that ?

(This is my first post, sry when i chose the wrong tag)

edited Jun 1 at 13:36

asked Jun 1 at 13:13

Nick Russler
21●4

You have chosen the wrong forum for this! Try posting it on stackoverflow.com -- you will get dozens of answers explaining how to solve your problem using dynamic programming. – TonyK Jun 1 at 13:20

isn't this also a mathematical problem ? Something like the Knapsack problem ? – Nick Russler Jun 1 at 13:36

here i got my answer: stackoverflow.com/questions/10852535/… – Nick Russler Jun 1 at 15:28

To summarize: The obvious greedy algorithm works. – Douglas Zare Jun 1 at 18:10

Browse other questions tagged algorithms integer-programming or ask your own question.

question feed