公式解説とは異なる基準で貪欲法を行っても解くことができます．以下のように貪欲法を行います．

• 割引価格の大きい順にクーポンを見ていく．クーポンを使用できる商品が存在するならば，その中で最も安い商品にクーポンを使用する．

以下，この方法を適用して得られる解のことを最適解と呼ぶことにします．

この貪欲法が正当であることの証明は，「最適解でない解を最適解と入れ替えたとき，損することはない」ことを示すことにより行えます．

最適解でない解には，次の 2 つのケースが考えられます．

• 使用できるはずのクーポンを使用しなかった．
• 使用できるはずのクーポンは使用したが，最も安い商品でない商品にクーポンを使用した．

これら 2 つのケースに対して，最適解と入れ替えても損をしないことを示します．以下では，割引価格の最も大きいクーポン（これを \(c_0\) とします）のみが貪欲法に従わず，それ以外のクーポンはすべて貪欲法に従った場合のみを考えることとします（そうでない場合でも，入れ替えを繰り返し適用させることにより，帰納的に示せます）．

まず，前者の場合を考えます．このとき，最適解において \(c_0\) を使用するはずだった商品（これを \(m\) とします），もしくはそれより高い商品に，実際に使用されたクーポンを，使われた商品の値段の安い順に \(c_1, c_2, \dots, c_k\) とします．

このとき，次のようなことが言えます．

• \(m\) に \(c_1\) が使用されていない場合：\(m\) に \(c_1\) を使用することで，その他のクーポンの使用状況も維持しながら，使えるクーポンを増やすことができる．
• \(m\) に \(c_1\) が使用されている場合： \(m\) に \(c_1\) ではなく，\(c_0\) を使用する．こうすることで，\(c_1\) は \(m\) に使用できなくなるが，代わりに次に安い商品に使用すればよい．ただ，この場合，\(c_k\) がどの商品にも適用できなくなる，といったことが考えられる．しかし，\(c_0\) の割引価格は \(c_k\) の割引価格よりは大きいため，全体で損をしているということはない．

次に，後者の場合を考えます．このとき，最適解において \(c_0\) を使用するはずだった商品を \(m_0\)，実際に使用した商品を \(m_1\) とします．このとき，次のようなことが言えます．

• \(m_0\) にクーポンが使用されていない場合：\(c_0\) の使用先を，\(m_1\) ではなく \(m_0\) に変更すればよい．このことにより，クーポンの使用状況は変わらず，なおかつほかのクーポンの使用先の選択肢が狭まることもない．

• \(m_0\) にクーポンが使用されている場合：\(m_0\) と \(m_1\) のクーポンの使用先を交換すればよい．\(m_1\) の値段は \(m_0\) 寄りも高いため，\(m_0\) に使用されていたクーポンは \(m_1\) にも使用できる．したがって，この入れ替えは常に可能であり，この入れ替えによって損をすることはない．

以上により，前者の場合も後者の場合も，最適解でない解を最適解と入れ替えて損をすることはないことが示されました．

実際に実装を行う際には，C++ では multiset などを用いることができます．

実装例（C++）