每种调料选or不选,选择某种调料意味着选中此酸度和苦度(酸度和苦度不要分开来看)
题目还要求至少选一种调料
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 15; int n, m; int s[maxn], b[maxn]; int ans = 0; int vis[maxn]; // 是否已被选过 int flag = 0; // 至少一种调料!!!!!!! void dfs(int x) // 第几个位置 { if (x > n) { int sum1 = 1; int sum2 = 0; for (int i = 1; i <= n; i++) { if (vis[i]) { sum1 *= s[i]; sum2 += b[i]; flag = 1; } } if (flag == 1) { ans = min(ans, abs(sum1 - sum2)); } flag = 0; return; } vis[x] = 1;//选 dfs(x + 1); vis[x] = 0;//不选 第一次写的时候忘记了-_- dfs(x + 1); } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> s[i] >> b[i]; } ans = abs(s[1] - b[1]); dfs(1); cout << ans; }