下記のような問題の答えを出力するプログラムを作ろうとしているのですが、アルゴリズムの設計方針が立ちません。
計算量が指数オーダーにならないような最適解、又は近似解を求めるアルゴリズムをご教授願えませんでしょうか。
また、回答をいただける際に可能でしたら、ある問題に直面した際のアルゴリズムの選定方法(どのように問題を捉えてどのようにアルゴリズムを選択、設計するか）も添えてご教授頂けたら幸いです。

[問題]

使用すると一定時間料金が安くなる3種のクーポンを持っている。
それぞれのクーポンは使用しても、使用してから一定時間後に再度使用が可能となる。
割引時間中は、いくつの物を買っても割引が適用される。
クーポンの種類は下記の通り。

(クーポン名, 割引率, 割引時間, 再度使用できるようになるまでの時間)
A, 10%, 10時間, 24時間
B, 20%, 7時間, 30時間
C, 30%, 2時間, 48時間

クーポンを併用することも可能だが、最終的な割引率は乗算で求められる。
例えば, 100円のものをA(10%)とB(20%)のクーポンを併用した場合は
(100円 * 0.9) * 0.8 = 72円

このとき、クーポンを一切使用しなかった人の購入した日時と価格が記された購入履歴が与えられた時、どのタイミングでどのクーポンを使用すると最も節約できたかを示せ。

図例
画像の説明をここに入力