CODEWITHSUNDEEP
algorithmgreedy
Vasile Turcu
Vasile Turcu

Reputation: 163

How to prove this greedy algorithm as optimal?

The problem sounds like this: we get n-cubes. Each cube has a length (the edge's length) and a colour. The edges' lengths are distinct, but the culours are not, for instance: any two cubes can never have the same length, but it is possible to have the same colour. The colours are from 1 to p (p is given).

We have to build a cube-tower that has a maximum height, following these rules:

1) a cube cannot be placed upon a cube if they have the same colour;

2) a cube cannot pe placed upon a cube whose edge's length is smaller.

e.g: cube c1 has a length of 3, cube c2 has a length of 5. cube c1 can be placed on the top of c2, but cube c2 cannot be placed on the top of c1.

Alright, so the algorithm I came up with in order to solve this problem is this:

  1. we sort the cubes by edge length, in descending order and we put them in an array;
  2. we add the first cube in the array to the Tower;
  3. we save the length of the last inserted cube( in this case, the first cube's length ) in variable l;
  4. we save the colour of the last inserted cube( in this case, the first cube's colour ) in variable c;
  5. we go through the rest of the array, inserting the first cube whose length is smaller than l and colour different than c and then we repeat 3-4-5;

Now what I'm having difficulties with is, how do I prove this greedy algorithm to be the optimal one? I guess that the proof has to somehow look like the ones here: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf

Upvotes: 0

Views: 584

Answers (1)

sascha
sascha

Reputation: 33512

The question is:

  • Is there a case where picking the max-length cube is not optimal?

At each decision-node we have to decide if we pick a or b, given a>b:

Assume picking b is strictly optimal (implies max-height):

  • Case 1: col(a) == col(b)
  • b optimal => final tower: b, x0, x1, ...
  • but also valid by construction with equal height: a, x0, x1, ...
  • valid because: col(a) == col(b), (a > b) & (b > x0) => (a > x0) (transitivity)

  • contradiction!

  • Case 2 col(a) != col(b)

  • b optimal -> final tower: b, x0, x1, ...
  • but also valid construction with more height: a, b, x0, x1, ...
  • valid because: (a > b) & (col(a) != col(b)) => a before b
  • contradiction!

We assumed picking b is strictly optimal and showed contradictions. Picking b can only be equally good or worse than picking a (the max-length cube of the remaining ones).

Upvotes: 2

Related Questions