Pythonで最も近いデザートコストを見つけるためのプログラム

baseCostsという2つの配列があり、そこからn個のアイテムがあり、baseとtoppingCostsがあり、それらからm個のアイテムがあり、トッピングを選択でき、ターゲット値もあります。デザートを作るには、これらのルールに従う必要があります。

• ベースは1つだけでなければなりません。

• 1つ以上のトッピングを追加することも、トッピングをまったく追加しないこともできます。

• トッピングの種類ごとに最大2つあります。

ここで、baseCosts [i]は、i番目のアイスクリームベースの価格を表します。 toppingCosts [i]は、i番目のトッピングの1つの価格を表します。目標値は、デザートの目標価格を表しています。総コストをできるだけ目標に近づけてデザートを作る必要があります。対象とするデザートの可能な限り最も近いコストを見つける必要があります。複数の回答がある場合は、下の方を返します。

したがって、入力がbaseCosts =[2,8]、toppingCosts =[4,5]、target =12のような場合、コスト8でベースを取得できるため、出力は12になり、最初のトッピングの1つをコストで取得できます。 4、タイプ2のトッピングがないため、合計コストは8 + 4=12です。

これを解決するには、次の手順に従います-

• best_cost：=baseCosts [0]

• 0からbaseCosts-1のサイズまでの範囲のbの場合、実行

  • bitmask：=サイズがtoppingCostsのサイズと同じで、0で埋められる配列

  • 次のことを無限に行います

    • current_price：=baseCosts [b]

    • 0からビットマスクのサイズ-1までの範囲のjの場合、実行

      • current_price：=current_price + bitmask [j] * toppingCosts [j]

    • current_price --targetが0と同じ場合、

      • ターゲットを返す

    • それ以外の場合|current_price--target | <| best_cost --target |、次に

      • best_cost：=current_price

    • それ以外の場合|current_price--target | | best_cost--target|と同じです。

      • current_price

        • best_cost：=current_price

    • 0がビットマスクになく、1がビットマスクにない場合、

      • ループから出てきます

    • 0からビットマスクのサイズまでの範囲のiの場合-1、実行

      • bitmask [i]が2と同じでない場合、

        • bitmask [i]：=bitmask [i] + 1

        • ループから出てきます

      • それ以外の場合

        • bitmask [i]：=0

• best_costを返す

例

理解を深めるために、次の実装を見てみましょう-

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