select n points out of m points all present on x-axis such that the sum of distances from each m point to its nearest nth selected point is minimum

153 Views Asked by At

The actual question is we are given 'm' areas and 'n' atm where n<=m. We have to station these 'n' atms in these 'm' areas so that the sum of distances between the areas and their nearest atm is minimum. eg: let there be 10 areas at x-axis at points {1,2,3,6,7,9,11,22,44,50}.So, the 5 atms should be stationed at {2,7,22,44,50} to get minimum sum of distances which is 9 since 1st area is at x=1 and its nearest atm is at x=2 ,so distance1=1 and similarly distance2=0, distance3=1, distance4=1, distance5=0, distance6=2, distance7=4, distance8=0, distance9=0, distance10=0