P2036 [COCI 2008/2009 #2] PERKET——题解

解题思路

每种食材只有“选”或“不选”两种决定，DFS 枚举全部子集，同时维护酸度乘积、苦度和以及是否已经选过食材。到达末尾时，对非空子集更新答案。

正确性说明

DFS 对每种食材完整枚举选与不选，因此覆盖所有子集；排除空集后，每个合法方案被计算一次，取所有绝对差的最小值即为答案。

复杂度分析

共 $2^n$ 个子集，时间复杂度 $O(2^n)$，递归空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,s[12],b[12]; long long ans=4e18;
void dfs(int i,long long ps,long long sb,bool chosen){
    if(i==n){if(chosen) ans=min(ans,llabs(ps-sb));return;}
    dfs(i+1,ps,sb,chosen);
    dfs(i+1,ps*s[i],sb+b[i],true);
}
int main(){cin>>n;for(int i=0;i<n;i++)cin>>s[i]>>b[i];dfs(0,1,0,false);cout<<ans<<'\n';return 0;}

#include <bits/stdc++.h> using namespace std; int n,s[12],b[12]; long long ans=4e18; void dfs(int i,long long ps,long long sb,bool chosen){ if(i==n){if(chosen) ans=min(ans,llabs(ps-sb));return;} dfs(i+1,ps,sb,chosen); dfs(i+1,ps*s[i],sb+b[i],true); } int main(){cin>>n;for(int i=0;i<n;i++)cin>>s[i]>>b[i];dfs(0,1,0,false);cout<<ans<<'\n';return 0;}