# find subset C (of size of k) of given array with minimal COST

input : set A of n distinct numbers and number k<=n output : (cost of) subset C of A of size k with the minimum COST(C)=max a∈A min c∈C |a − c|

the solution must define a recursive function and dynamic programming algorithm depending on the recursive function .

we define that the distance for element a(∈A) to subset C to be min c∈C |a-c| which means that the distance from an element to subset equal to the distance between the element and the closest element in subset e.g. : C={2,7,9} , a=5

min c∈C |a-c| = 2

input : set A of n distinct numbers and number k<=n output : (cost of) subset C of A of size k with the minimum COST(C)=max a∈A min c∈C |a − c|

the solution must define a recursive function and dynamic programming algorithm depending on the recursive function .

we define that the distance for element a(∈A) to subset C to be min c∈C |a-c| which means that the distance from an element to subset equal to the distance between the element and the closest element in subset e.g. : C={2,7,9} , a=5

``         min c∈C |a-c| = 2   ``

now example to illustrate the prblem let A={3,5,13,8} , K=2 (input) we consider all the subsets of A of size k: {3,5} , {3,13} , {3,8} , {5,13} , {5,8} , {13,8} for each subset we calculate the “distance” from each element to this subset and take the maximum

e.g. for subset {13,8} :

the distance between 3 and the subset is 5

the distance between 5 and the subset is 3

the distance between 8 and the subset is 0

the distance between 13 and the subset is 0

from all of this , we take the maximum which is 5 , we call COST and so on .. doing this for all the subsets and we want the subset with the minimum COST .(not the subset itself , it’s enough to return the cost for this subset)

my solution for the recursive function is :