様々な解法があります。
購入する1リットルのボトルの本数aと500ミリリットルのボトルの本数bについて、可能性のある範囲を全て試します。 必要な水の量Xの上限(20000以下)を考慮すると、1リットルのボトルは最大でも20本、500ミリリットルのボトルは最大でも40本まで試せばよいので、aを0から20、bを0から40の2重ループで、全ての組み合わせを試し、水の量がX以上の組み合わせについて、合計金額が最も少ない値を探します。
合計金額を求めるために、1リットルのボトルの本数aと500ミリリットルのボトルの本数bを求めることを考えます。
まず、問題を簡単にするために、必要な水の量Xが500で割り切れない場合、500で割り切れるように調整します。 例えば、Xが2400の場合は2500にすることで、その後の計算を単純化します。
次に、1リットルのボトルの価格Aと500ミリリットルのボトルの価格Bについて、以下の場合分けによって、最も少ない合計金額を求めます。
A < B
500ミリリットルのボトルより、1リットルのボトルの価格が安い場合は、1リットルのボトルのみで必要な量の水を購入します。
つまり、a = X/1000 + (Xが1000で割り切れない場合はもう1本)
A > 2*B 1リットルのボトル1本より、500ミリリットルのボトル2本の方が安い場合は、500ミリリットルのボトルのみで必要な量の水を購入します。 つまり、b = X/500
それら以外の場合、つまりB <= A <= 2B の場合
500ミリリットルの端数があれば、500 ミリリットルのボトルを1つ購入し、残りは1リットルのボトルで購入します。