Как да докажете този алчен алгоритъм като оптимален? - алгоритъм, алчен

Проблемът звучи така: получаваме n-кубчета. Всеки куб има дължина (дължина на ръба) и цвят. Дължините на ръбовете са различни, но колоните не са например: каквито и да са две кубчета никога няма да имат еднаква дължина, но е възможно да имат едни и същи цвят. Цветовете са от 1 до p (p е дадено).

Трябва да изградим кула-кула, която има максимална височина, следвайки тези правила:

1) куб не може да бъде поставен върху куб, ако има същия цвят;

2) куб не може да бъде поставен върху куб, чиято дължина на ръба е по-малка.

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

Добре, така че алгоритъмът, с който дойдох, за да разреша този проблем, е следният:

1. подреждаме кубовете по дължина на ръба, в низходящ ред и ги поставяме в масив;
2. добавяме първия куб в масива към Кулата;
3. ние запазваме дължината на последния вмъкнат куб (в този случай, дължината на първия куб) в променлива l;
4. запазваме цвета на последния вмъкнат куб (в този случай цвета на първия куб) в променлива c;
5. ние минаваме през останалата част от масива, като вмъкваме първия куб, чиято дължина е по-малка от l и цвят различен от c и след това повтаряме 3-4-5;

Сега това, с което имам трудности, е как мога да докажа, че този алчен алгоритъм е оптималният? Предполагам, че доказателството трябва да изглежда по някакъв начин като тези тук: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf

Отговори:

Въпросът е:

• Има ли случай, при който изваждането на максимум куб не е оптимално?

На всеки възел на решение трябва да решим дали ще вземем а или б, дадено а> б:

Да предположим, бране б е строго оптимално (предполага максимална височина):

• Случай 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
• противоречие!

Предполагахме, че брането е стриктно оптимално и показва противоречия. Изборът на б може да бъде еднакво добър или по-лош от това при вземането на (максимумният куб на останалите).