跳转至

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

问题描述#

你打算做甜点，现在需要购买配料。目前共有 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 。

示例 2：


输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：


输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：


输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

 

提示：

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

解题思路#

子集和问题。

方法一：三进制子集和生成加排序#

 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
class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        n = len(toppingCosts)
        N = 3 ** n
        dp = [0] * N

        for i in range(N):
            x, j = i, 0
            while x:
                dp[i] += (x % 3) * toppingCosts[j]
                j += 1
                x //= 3

        dp.sort()
        baseCosts.sort()

        n, L, R = len(baseCosts), 0, N - 1
        ans = baseCosts[0]

        while L < n and R >= 0:
            cur = baseCosts[L] + dp[R]
            if abs(cur - target) < abs(ans - target) or (abs(cur - target) == abs(ans - target) and cur < ans):
                ans = cur
            if cur == target:
                break
            elif cur > target:
                R -= 1
            else:
                L += 1

        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
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int n = toppingCosts.size();
        int N = pow(3, n);
        vector<int> dp(N);

        for (int i = 0; i < N; ++i) {
            int x = i, j = 0;

            while (x) {
                dp[i] += (x % 3) * toppingCosts[j++];
                x /= 3;
            }
        }

        sort(dp.begin(), dp.end());
        sort(baseCosts.begin(), baseCosts.end());

        int ans = baseCosts[0];
        int L = 0, R = N - 1;

        n = baseCosts.size();
        while (L < n && R >= 0) {
            int cur = baseCosts[L] + dp[R];

            if (abs(cur - target) < abs(ans - target) || (abs(cur - target) == abs(ans - target) && cur < ans)) {
                ans = cur;
            }

            if (cur == target) {
                break;
            } else if (cur > target) {
                --R;
            } else {
                ++L;
            }
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(3^n\log 3^n)\)
空间复杂度：\(\mathcal{O}(3^n)\)

方法二：生成有序的三进制子集和#

 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
def k_base_subset(nums: List[int], K: int):
    res = [0]

    for x in nums:
        Q = []
        for i in range(K):
            heapq.heappush(Q, (i * x, 0, i))

        tmp, n = [], len(res)
        while Q:
            d, i, k = heapq.heappop(Q)
            if i + 1 < n:
                heapq.heappush(Q, (res[i + 1] + k * x, i + 1, k))
            tmp.append(d)

        res = tmp

    return res

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        subset = k_base_subset(toppingCosts, 3)
        n, N = len(baseCosts), len(subset)
        L, R = 0, N - 1
        ans = baseCosts[0]

        baseCosts.sort()

        while L < n and R >= 0:
            cur = baseCosts[L] + subset[R]
            if abs(cur - target) < abs(ans - target) or (abs(cur - target) == abs(ans - target) and cur < ans):
                ans = cur
            if cur == target:
                break
            elif cur > target:
                R -= 1
            else:
                L += 1

        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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
vector<int> k_base_subset(vector<int> &nums, int K) {
    // 生成 k 进制排序子集
    vector<int> res{0};

    for (int x : nums) {
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> Q;

        for (int i = 0; i < K; ++i) {
            Q.emplace(i * x, 0, i);
        } 

        vector<int> tmp;
        int n = res.size();

        while (!Q.empty()) {
            auto [d, i, k] = Q.top();  Q.pop();

            if (i + 1 < n) {
                Q.emplace(res[i + 1] + k * x, i + 1, k);
            }

            tmp.emplace_back(d);
        }

        swap(res, tmp);
    }

    return res;
}

class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        auto subset = k_base_subset(toppingCosts, 3);

        int n = baseCosts.size(), N = subset.size();
        int L = 0, R = N - 1;
        int ans = baseCosts[0];

        sort(baseCosts.begin(), baseCosts.end());
        while (L < n && R >= 0) {
            int cur = baseCosts[L] + subset[R];

            if (abs(cur - target) < abs(ans - target) || (abs(cur - target) == abs(ans - target) && cur < ans)) {
                ans = cur;
            }

            if (cur == target) {
                break;
            } else if (cur > target) {
                --R;
            } else {
                ++L;
            }
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(3^n \log 3)\)
空间复杂度：\(\mathcal{O}(3^n)\)

方法三：动态规划#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        lim = max(baseCosts) + 2 * sum(toppingCosts)
        dp = [False] * (lim + 1)

        dp[0] = True
        for x in toppingCosts:
            for i in range(lim, x - 1, -1):
                dp[i] |= dp[i - x]
                if i - 2 * x >= 0:
                    dp[i] |= dp[i - 2 * x]

        ans = baseCosts[0]

        for x in baseCosts:
            for i in range(lim + 1):
                if dp[i]:
                    cur = i + x
                    if abs(cur - target) < abs(ans - target) or (abs(cur - target) == abs(ans - target) and cur < ans):
                        ans = cur

        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
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int lim = *max_element(baseCosts.begin(), baseCosts.end()) + 2 * accumulate(toppingCosts.begin(), toppingCosts.end(), 0);
        vector<int> dp(lim + 1);

        dp[0] = 1;
        for (int x : toppingCosts) {
            for (int i = lim; i >= x; --i) {
                dp[i] |= dp[i - x];
                if (i - 2 * x >= 0) {
                    dp[i] |= dp[i - 2 * x];
                }
            }
        }

        int ans = baseCosts[0];

        for (int x : baseCosts) {
            for (int i = 0; i <= lim; ++i) {
                if (dp[i]) {
                    int cur = i + x;
                    if (abs(cur - target) < abs(ans - target) || (abs(cur - target) == abs(ans - target) && cur < ans)) {
                        ans = cur;
                    }
                }
            }
        }

        return ans;
    }
};

时间复杂度：\(\mathcal{O}(m \times \lim)\)
空间复杂度：\(\mathcal{O}(\lim)\)

返回顶部

在手机上阅读