当前位置：首页 > news >正文

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

news 来源：原创 2024/4/27 9:37:51

题目链接

题意

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

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

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

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

思路

思路1：
n,m只有10，所以采用dfs或状态压缩枚举遍历每一种可能性。边界条件为把所有的配料枚举完。每次记录一下当前做的甜点的成本，维护最接近target的。
时间复杂度 $O(n*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
}