生活随笔
收集整理的這篇文章主要介紹了
LeetCode 1774. 最接近目标价格的甜点成本（DFS / 01背包）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
文章目錄
1. 題目
你打算做甜點(diǎn)，現(xiàn)在需要購買配料。目前共有 n 種冰激凌基料和 m 種配料可供選購。而制作甜點(diǎn)需要遵循以下幾條規(guī)則：
- 必須選擇 一種 冰激凌基料。
- 可以添加 一種或多種 配料，也可以不添加任何配料。
- 每種類型的配料 最多兩份 。
給你以下三個(gè)輸入：
baseCosts ，一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組，其中每個(gè) baseCosts[i] 表示第 i 種冰激凌基料的價(jià)格。
toppingCosts，一個(gè)長(zhǎng)度為 m 的整數(shù)數(shù)組，其中每個(gè) toppingCosts[i] 表示 一份 第 i 種冰激凌配料的價(jià)格。
target ，一個(gè)整數(shù)，表示你制作甜點(diǎn)的目標(biāo)價(jià)格。
你希望自己做的甜點(diǎn)總成本盡可能接近目標(biāo)價(jià)格 target 。
返回最接近 target 的甜點(diǎn)成本。
如果有多種方案，返回 成本相對(duì)較低 的一種。
示例
1：
輸入：baseCosts
= [1,7], toppingCosts
= [3,4], target
= 10
輸出：
10
解釋：考慮下面的方案組合（所有下標(biāo)均從
0 開始）：
- 選擇
1 號(hào)基料：成本
7
- 選擇
1 份
0 號(hào)配料：成本
1 x
3 = 3
- 選擇
0 份
1 號(hào)配料：成本
0 x
4 = 0
總成本：
7 + 3 + 0 = 10 。示例
2：
輸入：baseCosts
= [2,3], toppingCosts
= [4,5,100], target
= 18
輸出：
17
解釋：考慮下面的方案組合（所有下標(biāo)均從
0 開始）：
- 選擇
1 號(hào)基料：成本
3
- 選擇
1 份
0 號(hào)配料：成本
1 x
4 = 4
- 選擇
2 份
1 號(hào)配料：成本
2 x
5 = 10
- 選擇
0 份
2 號(hào)配料：成本
0 x
100 = 0
總成本：
3 + 4 + 10 + 0 = 17 。不存在總成本為
18 的甜點(diǎn)制作方案。示例
3：
輸入：baseCosts
= [3,10], toppingCosts
= [2,5], target
= 9
輸出：
8
解釋：可以制作總成本為
8 和
10 的甜點(diǎn)。返回
8 ，因?yàn)檫@是成本更低的方案。示例
4：
輸入：baseCosts
= [10], toppingCosts
= [1], target
= 1
輸出：
10
解釋：注意，你可以選擇不添加任何配料，但你必須選擇一種基料。提示：
n
== baseCosts
.length
m
== toppingCosts
.length
1 <= n
, m
<= 10
1 <= baseCosts
[i
], toppingCosts
[i
] <= 10^4
1 <= target
<= 10^4
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/closest-dessert-cost
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
2. 解題
class Solution {int ans
= INT_MAX
;int diff
= INT_MAX
;
public:int closestCost(vector
<int>& baseCosts
, vector
<int>& toppingCosts
, int target
) {int n
= baseCosts
.size(), m
= toppingCosts
.size();for(int i
= 0; i
< n
; i
++){dfs(toppingCosts
, 0, baseCosts
[i
], target
);}return ans
;}void dfs(vector
<int>& toppingCosts
, int idx
, int val
, int target
){if(abs(val
-target
) < diff
|| (abs(val
-target
)==diff
&& val
< ans
)){ans
= val
;diff
= abs(val
-target
);}if(idx
== toppingCosts
.size())return;dfs(toppingCosts
, idx
+1, val
, target
);dfs(toppingCosts
, idx
+1, val
+toppingCosts
[idx
], target
);dfs(toppingCosts
, idx
+1, val
+2*toppingCosts
[idx
], target
);}
};
12 ms 8.5 MB C++
- 更好的時(shí)間復(fù)雜度做法：https://leetcode-cn.com/problems/closest-dessert-cost/solution/zhuan-hua-wei-0-1bei-bao-qiu-jie-by-luci-o5yt/
- 將輔料數(shù)組追加一遍自己（最多使用兩次），跟基料（初始狀態(tài)）一起，使用01背包求解
我的CSDN博客地址 https://michael.blog.csdn.net/
長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！
總結(jié)
以上是生活随笔為你收集整理的LeetCode 1774. 最接近目标价格的甜点成本（DFS / 01背包）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
