1774. 最接近目标价格的甜点成本.md

1774. 最接近目标价格的甜点成本

题目传送门

点击这里

解题思路

题意很好理解，但是注意这道题并不是说得到最多份，要求是最接近成本，且如果有多种方案，返回成本相对较低的一种。以baseCosts中的每一种基料开始进行回溯方法来计算，在回溯的过程中的总花费一直增加，如果花费大于了target后，要计算一下差值比较，然后回溯。这道题可以转换一下，对于每一种基料，可以以【01】背包问题进行思考，所以这里的方法可以使用动态规划，以最少的基料v为起始，如果此时已经v >= target，则可以直接返回，否则我们对后续计算选择最小的一份，这里设定初始化为2 * target - x，原因是，大于该花费的方案于目标价格的差值一定大于，abs(x - target)的情况，背包的容量设置为target，设定动态规划数组dp[i]表示花费为i是否存在合法的方案，初始化是dp[baseCosts[i]] = true单独选择任意一个基料，每种配料最多使用两份，所以可以将配料看作有两个，当一个合法方案加上一个配料也必定是合法方案，可以得出dp[i] = dp[i-j]|dp[i] , i > j，每一个状态的求解只和前面的状态有关，从后往前更新即可。

代码

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	b := baseCosts[0]
	// 以最小的基准为底
	for _, v := range baseCosts {
		b = min(b, v)
	}
	var dfs func(i int, cur int)
	dfs = func(i int, cur int) {
		if abs(b-target) < cur-target { // 如果当前花费已经超过target且差值还大于结果，可以停止回溯
			return
		} else if abs(b-target) >= abs(cur-target) { // 如果当前花费的差值小于结果，考虑是否要继续添加配料
			if abs(b-target) > abs(cur-target) {
				b = cur
			} else {
				b = min(b, cur) // 如果差值相等，选择小的，用的是贪心思想
			}
		}
		if i == len(toppingCosts) { // 到达结尾
			return
		}
		dfs(i+1, cur+toppingCosts[i]*2) // 每一个最多两份
		dfs(i+1, cur+toppingCosts[i])
		dfs(i+1, cur) // 不添加
	}
	// 以其他基准开始计算，计算所有情况
	for _, v := range baseCosts {
		dfs(0, v)
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

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

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	b := baseCosts[0]
	for _, v := range baseCosts {
		b = min(b, v)
	}
	if b > target {
		return b
	}
	dp := make([]bool, target+1)
	res := 2*target - b // 最大情况
	for _, v := range baseCosts {
		if v <= target {
			dp[v] = true
		} else {
			res = min(res, v)
		}
	}
	for _, v := range toppingCosts {
		for count := 0; count < 2; count++ { // 每一个配料可以加两次
			for i := target; i > 0; i-- {
				if dp[i] && i+v > target { // 如果在花费成本为i时有可行方案，且i+v值大于了target，要比较一下和res的大小，res最开始是以最大值为基准。
					res = min(res, i+v) // i是合法方案，i+v一定也是合法方案，将大于target的方案选出最小值
				}
				if i-v > 0 { // 从后向前更新
					dp[i] = dp[i] || dp[i-v]
				}
			}
		}
	}
	// 在小于target的范围内查找，但是如果差值的绝对值比res-target大就没有必要，所以i的范围在[0, res-target]，这样target-i的范围就是[2*target-res, target]，由于res的范围是[target, 2*target - b]，所以如果target-i满足条件就会比res的结果贡献更小。
	for i := 0; i <= res-target; i++ {
		if dp[target-i] {
			return target - i
		}
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}