洛谷 P2036 [COCI 2008/2009 #2] PERKET深度优先搜索/位运算

题目链接

链接: P2036 [COCI 2008/2009 #2] PERKET

题目描述

解题思路

本题可以采用两种方法

这道题目需要在给定的可供选择的食材中，选择一些配料，使得总的酸度和总的苦度的绝对差最小。
首先，我们可以使用深度优先搜索DFS来尝试所有可能的选择组合。对于每一种食材，都有两种选择：选取或不选取。因此我们可以使用DFS来搜索所有可能的选择组合，并计算总的酸度和总的苦度的绝对差，最终取得最小的绝对差。

具体的实现细节如下：

1. 定义全局变量n表示可供选用的食材种类数，res表示当前的最小绝对差。

2. 定义数组a和b分别表示每种食材的酸度和苦度。

3. 编写DFS函数，函数参数包括当前遍历到的食材下标x，当前的酸度和苦度的乘积s，当前的苦度k。

4. 在DFS函数中，有两种情况：要么选择当前食材，要么不选择当前食材。递归地调用DFS函数来尝试所有可能的选择组合。

5. 当遍历到所有的食材后，更新res为当前的最小绝对差。

6. 在主函数中，读入n和每种食材的酸度和苦度，然后调用DFS函数得到最小的绝对差，并输出答案。

其次是位运算

首先，代码使用了一个整型变量res来记录当前的最小绝对差，初始化为一个较大的值inf。

然后，通过一个循环从1遍历到2^n-1（表示所有配料的选取情况），对于每一个数i，通过内层循环遍历每一种配料。

在内层循环中，代码通过(i>>u)&1来判断第u种配料是否被选取，如果被选取，则计算当前总的酸度sor和总的苦度ku，并更新res为当前酸度和苦度的绝对差的较小值。

最后输出res即为所求的最小绝对差。

这种方法利用了二进制表示来表示各种配料被选取的情况，通过遍历所有可能的选取组合，来求解最小的绝对差。这种方法在时间复杂度上虽然为O(2^n * n)，但在实际运行中因为常数项较小，所以可以在可接受的时间内得到结果。

代码实现

DFS

#include<bits/stdc++.h>
using namespace std;
const int N=11;
int n,res=0x3f3f3f3f;
int a[N],b[N];

void dfs(int x,int s,int k)
{
	if(x>=n){
		if(k==0) return;//如果没有选任何一种食材，则不能更新答案
		res=min(res,abs(s-k));
		return;
	}
	dfs(x+1,s*a[x],k+b[x]);
	dfs(x+1,s,k);
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i]>>b[i];
	dfs(0,1,0);
	cout<<res;
	return 0;
}

二进制枚举

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,res=inf;
int s[10],k[10];
int main()
{
   
	cin>>n;
	for(int i=0;i<n;i++) cin>>s[i]>>k[i];
	for(int i=1;i<(1<<n);i++)
	{
   
			int sor=1,ku=0;
			for(int u=0;u<n;u++)
			{
   
				if((i>>u)&1){
   
				 sor*=s[u];
				 ku+=k[u];
			    } 
		    }
			res=min(res,abs(sor-ku));
	}
	cout<<res<<endl;
	return 0;
}

总结

以上两种方法分别是使用深度优先搜索（DFS）和位运算来解决问题的。

深度优先搜索（DFS）方法的思路是通过递归遍历所有可能的选择组合。对于每一种食材，都有两种选择：选取或不选取。通过递归调用DFS函数来尝试所有可能的选择组合，并计算总的酸度和总的苦度的绝对差，最终取得最小的绝对差。这种方法的特点是直观易理解，但搜索的时间复杂度为指数级别，对于大规模的输入可能较慢。

位运算方法利用了二进制表示来表示各种配料被选取的情况。通过遍历所有可能的选取组合，来求解最小的绝对差。代码通过一个循环从1遍历到2^n-1（表示所有配料的选取情况），对于每一个数i，通过内层循环遍历每一种配料，通过(i>>u)&1来判断第u种配料是否被选取，并计算当前总的酸度和总的苦度，并更新最小的绝对差。这种方法的特点是时间复杂度较低，但需要对二进制表示和位运算有一定的理解。