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

题目描述

leetcode 中等题

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

• 必须选择 一种 冰激凌基料。
• 可以添加 一种或多种 配料，也可以不添加任何配料。
• 每种类型的配料 最多两份 。

给你以下三个输入：

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

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

示例1：

输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

提示1：

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 10^4
1 <= target <= 104

回溯

对每一种基料利用回溯模拟每个方案的成本。对于每个基料，每种配料存在三种可能：不加入\加入一次\加入两次。并且显然当某个方案的成本超出了 $target$ 时，可以不再往下搜索，因为继续往下差距只会继续拉大。

class Solution {
    int[] toppingCosts;
    int target;
    int ans;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
       ans = Arrays.stream(baseCosts).min().getAsInt();
       this.toppingCosts = toppingCosts;
       this.target = target;
       for(int item : baseCosts){
           dfs(0, item); 
       }
       return ans;
    }

    private void dfs(int p, int curCost){
        if(Math.abs(target - ans) < Math.abs(target - curCost) && target < curCost){
            return;
        }
        if(Math.abs(target - ans) == Math.abs(target - curCost)){
            ans = Math.min(ans, curCost);
        }
        if(Math.abs(target - ans) > Math.abs(target - curCost)){
            ans = curCost;
        }
        if(p == toppingCosts.length){
            return;
        }
        dfs(p + 1, curCost);
        dfs(p + 1, curCost + toppingCosts[p]);
        dfs(p + 1, curCost + (toppingCosts[p] * 2));
    }
}

枚举 + 二分查找左边界

每种配料最多可以选两次，我们可以把每种配料看作存在两份，类似 $[top1, top2, top1, top2]$ ，那么对于某种方案，就可以视为拆分后每个配料只存在两种情况，加入或者不加入。接着我们可以枚举其中一半的拆分后配料的子集和，然后通过二分查找得到使总和最接近 $target$ 的另一半配料的成本和。

稍微要注意的是，这里我们通过二分查找搜索的是左边界，也就是说最接近的下标只可能是 $\{left, left - 1\}$ 。

class Solution {
    private List<Integer> arr = new ArrayList<>();
    private int[] toppingCosts;
    private int inf = 1 << 30;

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        this.toppingCosts = toppingCosts;
        dfs(0, 0);
        Collections.sort(arr);
        int ans = inf;
        for (int x : baseCosts) {
            // 枚举子集和
            for (int y : arr) {
                // 二分查找
                int i = search(target - x - y);
                for (int j : new int[] {i, i - 1}) {
                    if (j >= 0 && j < arr.size()) {
                        int curCost = x + y + arr.get(j);
                        if (Math.abs(ans - target) > Math.abs(curCost - target) 
                        || (Math.abs(ans - target) == Math.abs(curCost - target) && ans > curCost)) {
                            ans = curCost;
                        }
                    }
                }
            }
        }
        return ans;
    }

    private void dfs(int i, int t) {
        if (i >= toppingCosts.length) {
            arr.add(t);
            return;
        }
        dfs(i + 1, t);
        dfs(i + 1, t + toppingCosts[i]);
    }

    private int search(int x) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr.get(mid) < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

}

枚举 + 二分查找右边界

类似的，可以使用二分查找右边界的方法进行搜索，此时最接近的下标只可能是 $\{left - 1, left\}$ 。

...
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
                ...
                for (int j : new int[] {i, i + 1}) {
                ...
    }
...
    private int search(int x) {
        int left = 0, right = arr.size();
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr.get(mid) > x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }
...

动态规划

将问题转换成某个成本是否存在可行方案的问题，然后选择最接近目标的成本即可，此时问题转换成了 01背包。

$dp[i]$ 为 $true$ 表示 $i$ 成本存在可行方案，初始化为 $false$ 表示不存在。

当某个基料已经大于 $target$ 时，这种情况不应该选择配料，因为选择配料只会使差距更大，并且大于 target 的合法成本只需要保留最小的一份即可，所以背包容量设为 $target$ 即可。

并且由于单独选择基料是合法的，所以如果存在 $base[x] = i$ ，那么 $dp[i] = true$。

接下来类似 01背包 枚举配料的选择，由于每个配料最多选择两次，所以类似上面二分查找的解法，将每种配料视为存在两种。

任意一个合法方案加一份配料也为合法方案，所以当前配料成本为 $y$ 时，对于开销 $c$ ，转移方程为：

$$
\begin{align}
&dp(c)　 |=　dp(c - y)　　　　　　　　　　　　　　　　　　　 c > y\\
\end{align}
$$

class Solution {
    public int closestCost(int[] base, int[] top, int target) {
        boolean[] dp = new boolean[target + 5];
        int ans = Integer.MAX_VALUE;
        for (int x : base) { 
            if (x > target) ans = Math.min(ans, x); // 只选基料
            else dp[x] = true;
        }
        for (int x : top) {
            for (int i = 0; i < 2; i++) { // 拆分成两份
                for (int j = target; j >= 0; j--) {
                    if (dp[j] && j + x > target) ans = Math.min(ans, j + x); // 大于 target 的合法成本只需要保留最小的一份即可
                    if (j > x) dp[j] |= dp[j - x];
                }
            }
        }
        for (int i = target; i >= 0; i--) {
            if(target - i > ans - target){
                // 剩余的只会比 ans 差距更大
                break;
            }
            if (dp[i]) return i;
        }
        return ans;
    }
}