Зафиксируем какое-нибудь оптимальное решение и наше жадное решение. Будем рассматривать походы за шубами в хронологическом порядке и сравнивать эти походы в оптимальном и в жадном решении. Допустим мы нашли различающийся поход, в этом походе будет какой-то (возможно, пустой) совпадающий префикс, потом первые различающиеся элементы, потом какой-то (возможно, пустой) суффикс. Введем обозначение:

А — последний элемент префикса (он совпадает в обоих походах)

x_greedy — шуба, выбранная жадником

x_opt — шуба из оптимального решения

В оптимальном алгоритме мы все-таки когда-то возьмем шубу x_greedy. Обозначим шубу, предшествующую x_greedy в оптимальном решении как B.

Так как в жадном алгоритме мы берем всегда минимальную шубу и так как шубы, выбранные жадником и оптимальным алгоритмом не равны, получаем что x_greedy < x_opt.

Поменяем в оптимальном решении местами суффиксы, начинающиеся с x_opt и x_greedy (включая сами x_greedy и x_opt), то есть а оптимальном решении после А будем брать x_greedy, а после B — x_opt. Решение при этом останется правильным, потому что:

1. После элемента А мы можем взять x_greedy, потому что x_greedy подходит туда в жадном решении, то есть между A и х_greedy есть необходимая разница.

2. После элемента B мы можем взять x_opt вместо x_greedy, потому что x_opt > x_greedy, такая замена очевидно не портит решение.

Таким образом мы сделали оптимальное решение немножко более похожим на жадное. При этом решение не потеляло в стоимости, потому что мы не добавляли походов. Проведя такую манипуляцию несколько раз можно из оптимального решения получить наше жадное. Так как при этих действиях стоимость решения не меняется, то значит, что наше жадное решение имеет такую же стоимость, как оптимальное.