Cpp 算法题：Perket 食谱 - 最小酸味和苦味差值 - 常规

题目描述： 'Perket' 是一道众所周知的美味佳肴。为了使 'Perket' 保持原样，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最大的味道。

您有 N 种成分可供使用。对于每种食物，我们都知道它的酸度 S 和苦味 B。当使用多种成分时，总酸度是所有成分的酸度量的乘积，总苦味是所有成分苦味量的总和。

众所周知，'Perket' 既不酸也不苦。我们要选择成分，以使酸味和苦味之间的绝对差最小。

另外，必须使用至少一种成分。你不能把水当做主菜。

输入格式第一行包含整数 N（1≤N≤10），这是我们可以使用的成分数。

接下来的 N 行中的每行包含两个整数，每个整数之间用空格隔开，即每种成分的酸味和苦味。

输入数据将是这样的，如果我们用所有成分做饭，酸味和苦味都将小于 1000000000。

输出格式输出酸味和苦味之间的最小差异。

输入输出样例样例 1 输入样例复制 1 3 10

输出样例复制 7 样例 2 输入样例复制 2 3 8 5 8

输出样例复制 1 样例 3 输入样例复制 4 1 7 2 6 3 8 4 9 输出样例复制 1 样例说明在第三个示例中，我们选择最后三种成分。那么总酸味为2·3·4 = 24，苦味为6 + 8 + 9 = 23。区别是1。

思路：

给定N种成分的酸度和苦味，我们要选择一部分成分，使得它们的酸度乘积和苦味之和之间的差值最小。
可以使用回溯法来解决这个问题。从第一种成分开始，逐个选择或不选择，计算每种选择情况下的酸度乘积和苦味之和的差值。
使用递归函数backtrack来实现回溯。
- 参数cur表示当前考虑的成分的索引。
- 参数s表示当前已选择的成分的酸度乘积。
- 参数b表示当前已选择的成分的苦味之和。
- 参数diff表示当前已选择的成分的酸度乘积和苦味之和的差值。
- 参数sTotal表示所有成分的酸度乘积。
- 参数bTotal表示所有成分的苦味之和。
- 参数chosen表示当前已选择的成分的状态。
- 参数minDiff表示当前最小的差值。
在回溯函数中，首先判断是否选择了所有的成分，如果是，则更新最小差值。
然后，对于当前的成分，有两种选择：选择或不选择。
- 如果选择了当前成分，更新酸度乘积、苦味之和和差值，并递归调用回溯函数，处理下一个成分。
- 如果不选择当前成分，直接递归调用回溯函数，处理下一个成分。
在回溯函数结束后，返回最小差值。

伪代码：

function backtrack(cur, s, b, diff, sTotal, bTotal, chosen, minDiff)
    if cur == N
        minDiff = min(minDiff, abs(sTotal - bTotal))
        return
    end if

    // 选择当前成分
    chosen[cur] = true
    backtrack(cur + 1, s * S[cur], b + B[cur], abs(s * S[cur] + b + B[cur] - sTotal + bTotal), sTotal, bTotal, chosen, minDiff)

    // 不选择当前成分
    chosen[cur] = false
    backtrack(cur + 1, s, b, diff, sTotal, bTotal, chosen, minDiff)
end function

function findMinDiff(N, S, B)
    sTotal = 1
    bTotal = 0
    for i = 0 to N-1
        sTotal = sTotal * S[i]
        bTotal = bTotal + B[i]
    end for

    chosen = [false] * N
    minDiff = INF
    backtrack(0, 1, 0, abs(1 + 0 - sTotal + bTotal), sTotal, bTotal, chosen, minDiff)

    return minDiff
end function

N = readInt()
S = [0] * N
B = [0] * N
for i = 0 to N-1
    S[i], B[i] = readInt(), readInt()
end for

minDiff = findMinDiff(N, S, B)
print(minDiff)

复杂度分析：

时间复杂度：回溯函数的时间复杂度为O(2^N)，其中N为成分的数量。每个成分有两种选择：选择或不选择。总共有2^N种选择情况。计算每种选择情况下的酸度乘积和苦味之和的差值的时间复杂度为O(1)。所以总时间复杂度为O(2^N)。
空间复杂度：回溯函数的空间复杂度为O(N)，用于存储当前已选择的成分的状态。递归调用的最大深度为N。所以总空间复杂度为O(N)。