以下の貪欲法により解くことができます。

• 値段の安い順に商品を見ていき、使えるクーポンがあるならばその中で最も \(D_i\) が大きいクーポンを使用して商品を買う。使えるクーポンが存在しない場合定価で商品を買う。

この貪欲法は優先度付きキューなどを用いて実装可能で、 \(\mathrm{O}((N+M)\log M)\) で動作します。

貪欲法の正当性は、この問題は結局使用したクーポンの \(D_i\) の総和を最大化する問題であり、使用可能なクーポンはできる限り早く使っても損しないことから従います。