資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 程式查詢最接近的甜點成本
假設我們有兩個陣列，稱為 baseCosts，其中包含 n 個專案，我們可以從中選擇基礎，toppingCosts，其中包含 m 個專案，我們可以從中選擇澆頭，並且還有一個目標值。我們必須遵循以下規則來製作甜點。
必須恰好有一個基礎。
我們可以新增一個或多個澆頭，或者根本不新增澆頭。
每種澆頭的數量最多為兩個。
這裡 baseCosts[i] 表示第 i 個冰淇淋基礎的價格。toppingCosts[i] 表示第 i 個澆頭的價格。目標值表示甜點的目標價格。我們必須製作一個總成本儘可能接近目標的甜點。我們必須找到甜點最接近目標的可能成本。如果有多個答案，則返回較小的那個。
因此，如果輸入類似於 baseCosts = [2,8]，toppingCosts = [4,5]，target = 12，則輸出將為 12，因為我們可以選擇成本為 8 的基礎，然後選擇成本為 4 的第一個澆頭 1 個，並且不選擇型別 2 的澆頭，所以總成本為 8+4 = 12。
為了解決這個問題，我們將遵循以下步驟 -
best_cost := baseCosts[0]
對於 b 從 0 到 baseCosts 大小 - 1，執行
bitmask := 一個大小與 toppingCosts 大小相同的陣列，並用 0 填充
無限迴圈執行以下操作：
current_price := baseCosts[b]
對於 j 從 0 到 bitmask 大小 - 1，執行
current_price := 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 且 bitmask 中沒有 1，則
退出迴圈
對於 i 從 0 到 bitmask 大小 - 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
169 次檢視
