Як довести цей жадний алгоритм як оптимальний? - алгоритм, жадібний

Проблема звучить так: ми отримуємо n-кубики.Кожен куб має довжину (довжину краю) і колір. Довжини країв різняться, але кульори - ні, наприклад: будь-які два кубики ніколи не можуть мати однакову довжину, але можна мати однакову довжину колір. Кольори від 1 до p (задано p).

Ми повинні побудувати куб-вежу, яка має максимальну висоту, дотримуючись наступних правил:

1) куб не можна розміщувати на кубі, якщо вони мають однаковий колір;

2) куб не можна покласти на куб, довжина краю якого менша.

наприклад: куб c1 має довжину 3, куб c2 має довжину 5. куб c1 можна розмістити на вершині c2, але куб c2 не можна розмістити на вершині c1.

Гаразд, отже, алгоритм, який я придумав для вирішення цієї проблеми, такий:

1. сортуємо кубики за довжиною ребра, за спаданням, і розміщуємо їх у масив;
2. ми додаємо перший куб у масиві до Tower;
3. ми зберігаємо довжину останнього вставленого куба (в даному випадку довжини першого куба) у змінну l;
4. ми зберігаємо колір останнього вставленого куба (в даному випадку - кольору першого куба) у змінну c;
5. ми проходимо решту масиву, вставляючи перший куб, довжина якого менше l, а колір відрізняється від c, а потім повторюємо 3-4-5;

Тепер, з чим у мене виникають труднощі, це те, як мені довести цей жадібний алгоритм як оптимальний? Я думаю, доказ повинен якось виглядати так, як тут: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf

Відповіді:

Питання в тому, що:

• Чи є випадок, коли вибір куба максимальної довжини не є оптимальним?

На кожному вузлі рішення ми повинні вирішити, чи будемо обирати a або б, дано a> b:

Припустимо, що вибір b є строго оптимальним (передбачає максимальну висоту):

• Справа 1: col(a) == col(b)
• b optimal => final tower: b, x0, x1, ...
• але також дійсний за конструкцією з однаковою висотою: a, x0, x1, ...
• дійсний, оскільки: col(a) == col(b), (a > b) & (b > x0) => (a > x0) (транзитивність)

• суперечність!

• Справа 2 col(a) != col(b)

• b optimal -> final tower: b, x0, x1, ...
• але також допустима конструкція з більшою висотою: a, b, x0, x1, ...
• дійсний, оскільки: (a > b) & (col(a) != col(b)) => a before b
• суперечність!

Ми припустили, що вибір b є строго оптимальним і показав суперечності. Вибір b може бути однаково хорошим або гіршим, ніж підбір a (куб максимальної довжини решти).