你打算做甜點(diǎn)，現(xiàn)在需要購買配料。目前共有 n 種冰激凌基料和 m 種配料可供選購。而制作甜點(diǎn)需要遵循以下幾條規(guī)則：
1、必須選擇 一種 冰激凌基料。
2、可以添加 一種或多種 配料，也可以不添加任何配料。
3、每種類型的配料 最多兩份 。
給你以下三個輸入：
1、baseCosts ，一個長度為 n 的整數(shù)數(shù)組，其中每個 baseCosts[i] 表示第 i 種冰激凌基料的價格。
2、toppingCosts，一個長度為 m 的整數(shù)數(shù)組，其中每個 toppingCosts[i] 表示 一份 第 i 種冰激凌配料的價格。
3、target ，一個整數(shù)，表示你制作甜點(diǎn)的目標(biāo)價格。
你希望自己做的甜點(diǎn)總成本盡可能接近目標(biāo)價格 target 。
返回最接近 target 的甜點(diǎn)成本。如果有多種方案，返回 成本相對較低 的一種。
示例 1：輸入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
輸出：10
解釋：考慮下面的方案組合（所有下標(biāo)均從 0 開始）：
輸入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
輸出：17
解釋：考慮下面的方案組合（所有下標(biāo)均從 0 開始）：
輸入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
輸出：8
解釋：可以制作總成本為 8 和 10 的甜點(diǎn)。返回 8 ，因為這是成本更低的方案。
示例 4：
輸入：baseCosts = [10], toppingCosts = [1], target = 1
輸出：10
解釋：注意，你可以選擇不添加任何配料，但你必須選擇一種基料。
本題使用了回溯算法，根據(jù)規(guī)則，基料必須選擇一種，而配料可以不選或者最多選擇兩種，故先選擇第一種基料去嘗試配料和可能的配料個數(shù)。由于配料都為正數(shù)，當(dāng)成本大于最優(yōu)的方案時進(jìn)行回溯。
代碼
重慶分公司
重慶分公司
class Solution {int res; //存儲最優(yōu)值
public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {res = Arrays.stream(baseCosts).min().getAsInt(); //取出基料中成本最低的
for (int b:baseCosts) {//遍歷每一種基料
def(toppingCosts,0,b,target);
}
return res;
}
private void def(int[] toppingCosts, int i, int cur, int target) {if (Math.abs(res - target)< cur - target) {return;
}else if (Math.abs(res - target) >= Math.abs(cur - target)){if (Math.abs(res - target) >Math.abs(cur - target)) {res = cur;
}else {res = Math.min(res,cur);
}
}
if (i == toppingCosts.length) {return;
}
def(toppingCosts,i+1,cur+toppingCosts[i] * 2,target);
def(toppingCosts,i+1,cur+toppingCosts[i],target);
def(toppingCosts,i+1,cur,target);
}
}你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
