Проблема звучит так: мы получаем n-кубов. Каждый куб имеет длину (длину края) и цвет. Длины краев различны, но кулоры не являются, например: любые два куба никогда не могут иметь одинаковую длину, но можно иметь один и тот же цвет. Цвета от 1 до p (p задано).Как доказать этот жадный алгоритм как оптимальный?
Мы должны построить куб башню, которая имеет максимальную высоту, следуя этим правилам:
1) куб не может быть помещен на куб, если они имеют один и тот же цвет;
2) куб не может быть размещен на кубе, длина которого меньше.
например: cube c1 имеет длину 3, куб c2 имеет длину 5. Куб c1 может быть помещен в верхнюю часть c2, но куб c2 не может быть размещен в верхней части c1.
Хорошо, так что алгоритм я придумал для того, чтобы решить эту проблему следующим образом:
- мы сортируем кубики от длины кромки, в порядке убывания, и мы помещаем их в массив;
- мы добавляем первый куб в массив к Башне;
- Мы сохраняем длину последнего вставленного куба (в данном случае длину первого куба) в переменной l;
- Мы сохраняем цвет последнего вставленного куба (в данном случае, цвет первого куба) в переменной c;
- мы проходим остаток массива, вставляя первый куб, длина которого меньше l и цвет отличается от c, а затем повторяем 3-4-5;
Теперь у меня возникают трудности с тем, как я могу доказать, что этот жадный алгоритм является оптимальным? Я думаю, что доказательство должно так или иначе похожи на те здесь: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf
@trincot куба не может иметь одинаковую длину, я говорил об этом, когда я объяснил проблему: «любые два куба никогда не могут иметь такую же длину» –
Ах, да. пропустил это. Таким образом, тест * ", длина которого меньше 1 * * на шаге 5, действительно не требуется, так как это всегда будет иметь место для всех последующих кубов. – trincot
@ trincot Правда, правда, я написал, что только для того, чтобы быть более ясным, я думаю. –