Pythonでターゲットに最も近いデザートのコストを求めるプログラム

問題の概要

n 個の要素を持つ配列 baseCosts（アイスクリームのベースの価格一覧）と、m 個の要素を持つ配列 toppingCosts（トッピングの価格一覧）、そして目標金額 target が与えられます。次のルールに従ってデザートを作ります。

• ベースは必ずちょうど1つ選ぶ。

• トッピングは1種類以上追加してもよいし、まったく追加しなくてもよい。

• 同じ種類のトッピングは最大2つまで使用できる。

baseCosts[i] は i 番目のアイスクリームベースの価格、toppingCosts[i] は i 番目のトッピング1つの価格を表します。target はデザートの目標価格です。合計コストができるだけ target に近くなるようなデザートを作り、その最も近いコストを求めます。条件を満たす答えが複数存在する場合は、より小さい方の値を返してください。

たとえば、入力が baseCosts = [2,8]、toppingCosts = [4,5]、target = 12 の場合、出力は 12 になります。これは、コスト8のベースを選び、コスト4の1番目のトッピングを1つ追加し、2番目のトッピングは使わないことで、合計が 8 + 4 = 12 となり、ちょうど目標に一致するためです。

解き方のアプローチ

この問題は、各トッピングの使用数（0個・1個・2個）をビットマスク配列で管理しながら全探索することで解けます。手順は以下のとおりです。

• best_cost を baseCosts[0] で初期化する。

• b を 0 から baseCosts のサイズ - 1 まで繰り返す。

  • bitmask を toppingCosts と同じサイズの配列として用意し、すべて 0 で初期化する。

  • 以下を無限に繰り返す。

    • current_price を baseCosts[b] で初期化する。

    • j を 0 から bitmask のサイズ - 1 まで繰り返し、current_price に bitmask[j] × toppingCosts[j] を加算する。

    • current_price - target が 0 なら、target を返す。

    • |current_price - target| < |best_cost - target| なら、best_cost を current_price に更新する。

    • |current_price - target| が |best_cost - target| と等しく、かつ current_price < best_cost なら、best_cost を current_price に更新する。

    • bitmask に 0 も 1 も含まれていない場合（すべて 2 の場合）は、これ以上の組み合わせがないのでループを抜ける。

    • i を 0 から bitmask のサイズ - 1 まで繰り返し、bitmask[i] が 2 以外なら 1 増やして抜ける。2 であれば 0 に戻す（桁上がりのように扱う）。

• 最後に best_cost を返す。

計算量について

各トッピングの使い方は「0個 / 1個 / 2個」の3通りなので、1つのベースに対するトッピングの組み合わせは最大 3^m 通りになります。したがって全体の計算量は O(n × 3^m) です。制約が小さい問題では、この全探索で十分に間に合います。

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(baseCosts, toppingCosts, target):
    best_cost = baseCosts[0]

    for b in range(len(baseCosts)):
        bitmask = [0] * len(toppingCosts)
        while True:
            current_price = baseCosts[b]
            for j in range(len(bitmask)):
                current_price += bitmask[j] * toppingCosts[j]
            if current_price - target == 0:
                return target
            elif abs(current_price - target) < abs(best_cost - target):
                best_cost = current_price
            elif abs(current_price - target) == abs(best_cost - target):
                if current_price < best_cost:
                    best_cost = current_price

            if 0 not in bitmask and 1 not in bitmask:
                break
            for i in range(len(bitmask)):
                if bitmask[i] != 2:
                    bitmask[i] += 1
                    break
                else:
                    bitmask[i] = 0
    return best_cost

baseCosts = [2,8]
toppingCosts = [4,5]
target = 12
print(solve(baseCosts, toppingCosts, target))

入力

[2,8], [4,5], 12

出力

12

まとめ

ベースを1つずつ固定しながら、トッピングの使用数を3進数的なビットマスクで列挙していくことで、目標金額に最も近いデザートのコストを効率よく求められます。距離が同じ場合はより小さい値を採る処理を忘れないこと、そして合計が target に一致した時点で即座に返すことで無駄な探索を省けることがポイントです。