【力扣·每日一题】1774. 最接近目标价格的甜点成本 (dfs搜索 动态规划 Go)

题目链接

题意

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

必须选择 一种 冰激凌基料。
可以添加 一种或多种 配料，也可以不添加任何配料。
每种类型的配料 最多两份 。
给你以下三个输入：

baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
target ，一个整数，表示你制作甜点的目标价格。
你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

思路

思路1：
n,m只有10，所以采用dfs或状态压缩枚举遍历每一种可能性。边界条件为把所有的配料枚举完。每次记录一下当前做的甜点的成本，维护最接近target的。
时间复杂度 $O(n\ast 3^m)$
思路2：
实际上是个背包问题

代码

var ans int
var target int 
var toppingCosts []int

func abs(x int) int {
    if x >= 0 {
        return x
    }
    return -x
}

func dfs(cnt, now int) {
   if abs(ans-target) >= abs(now-target) {
        if  abs(ans-target) > abs(now-target) {
            ans = now
        }else{
            if ans > now {
                ans = now
            }
        }
    }
    if cnt == len(toppingCosts) {
        return 
    }
    dfs(cnt+1,now+toppingCosts[cnt]*2)
    dfs(cnt+1,now+toppingCosts[cnt])
    dfs(cnt+1,now)
}

func closestCost(baseCosts []int, toppingCosts1 []int, target1 int) int {
    target = target1
    toppingCosts = toppingCosts1
    //回溯
    ans = 100000
    for _,val := range baseCosts {
        if ans > val {
            ans = val
        }
    }
    for _,val := range baseCosts {
        dfs(0,val)
    }
    return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44