dfs 枚举每种物品用了还是没用

#include <bits/stdc++.h>
using namespace std;
int n;
int s[15], b[15];
int ans;
// 当前考虑第 now 种食物，之前的总酸度为 x，总苦度为 y
void dfs(int now, int x, int y)
{
    // 前 n 种都考虑完了，就算算能不能优化答案
    if (now == n + 1)
    {
        if (!(x == 1 && y == 0))
            ans = min(ans, abs(x - y));
        return;
    }
    // 考虑第 now 种用还是不用
    dfs(now + 1, x, y);
    dfs(now + 1, x * s[now], y + b[now]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> b[i];
    ans = abs(s[1] - b[1]);
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}

位运算枚举所有可能性

#include <bits/stdc++.h>
using namespace std;
int n;
int s[15], b[15];
int ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i] >> b[i];
    ans = abs(s[1] - b[1]);
    // 当前物品选择方案为 sta 的二进制结果
    for (int sta = 1; sta <= (1 << n) - 1; sta++)
    {
        // 枚举每个二进制位，如果为 1，说明选择了对应的物品
        int x = 1;
        int y = 0;
        // 0~n-1 对应了第 1~n 件物品
        for (int i = 0; i <= n - 1; i++)
            if (sta & (1 << i))
            {
                // 选择了第 i+1 件物品
                x *= s[i + 1];
                y += b[i + 1];
            }
        ans = min(ans, abs(x - y));
    }
    cout << ans;
    return 0;
}