We have a group 'S' that contains 2n socks. each sock in the group has a color. Colors are represented by a real positive number. [c : S -> R(+)] It is possible for 2 socks in the group to be in the same color.
-We define "Punishment" of a pair of socks (a,b) like that: P(a,b) = |c(a)-c(b)|. (in other word the "punishment" of 2 socks of the same color is 0)
I need to describe a greedy algorithm that gets as input a group S and returns a group A that contains pairs of socks (each sock from S, is in A exactly one time) and the summarize punishment will be minimal. [summarize punishment=> the sum of punishments of all the pairs in the group]
and I need to prove that the algorithm is correct. I'm having problem with proving my algorithm is correct, I sorted the socks according to their numeric color value , and picked the first ones from S each time. I tried to prove it with induction but I don't know how I need to do the 'switching' part in the optimal group.
So your algorithm is correct :)
Proof: Imagine, that we have different solution to our problem which is better one than ours(we just sorted and matched nearest together). Therefore there must exist at least two pairs (a
1) a is in interval (c,d) and b isnt or similar to them.
(otherwise we would have this pairs in our solution).
Now lets calculate the punishment: punishment is |a-b| + |c-d|
because of our 1) we can think about the order of our numbers such as:
2 : a < c < b < d
3 : a < c < d < b
4 : c < a < b < d
5 : c < a < d < b
Each orther is almost the same in calculations: we can easily prove
for example in (2) that |a-b| + |c-d| > |a-c| + |b-d|,
because a-b < a-c and a < c < b so |a-b| > |a-c| c-d < b-d and c < b < d so |c-d| > |b-d|
Now if that happen, swapping those values will change this solution to even better one which is looking like in our algorithm :)