题目分析

1. 目标：根据给定的比赛规则，找出盈利能力指数最高的部门，并输出相关信息，包括盈利能力指数、总销售额、总开发成本、实现的功能列表以及满足的客户列表。
2. 输入数据：
   • 第一行为数据集的数量。
   • 每个数据集的第一行包含四个整数，分别表示最小成本、最大成本、潜在功能数量（\(N\leq20\)）、潜在客户数量（\(M\leq20\)）。
   • 接下来的\(N\)行，每行给出一个功能的开发成本。
   • 接下来的\(M\)行，每行描述一个客户的需求，格式为：所需功能数量 功能编号列表 销售额。
3. 输出数据：
   • 每个数据集的输出格式如下：
     • 第一行：Feature Set \(N\)（\(N\)从\(1\)开始）。
     • 第二行：盈利能力指数（保留三位小数）。
     • 第三行：总销售额。
     • 第四行：总开发成本。
     • 第五行：实现的功能列表（按编号升序排列，空格分隔）。
     • 第六行：满足的客户列表（按编号升序排列，空格分隔）。
4. 规则：
   • 获胜部门需满足其盈利能力指数（销售额 / 开发成本）最大。
   • 每个部门的开发成本必须控制在给定的最小值和最大值范围内。
   • 如果两个部门的盈利能力指数相同（四舍五入到三位小数后相等），则选择利润更高（销售额 - 开发成本）的部门。
   • 若仍相同，选择开发功能数量更少的部门。
   • 若仍相同，选择满足客户数量更多的部门。

解题思路

1. 预处理：
   • 计算\(2\)的幂次方，存储在\(expV\)数组中，方便后续位运算。
   • 初始化一些变量，如\(maxPI\)、\(maxPM\)、\(minFN\)等。
2. 枚举功能组合：
   • 使用位运算枚举所有可能的功能组合。对于每个功能组合，计算其开发成本\(curCost\)和功能数量\(curFN\)。
   • 如果\(curCost\)不在给定的成本范围内，则跳过该组合。
3. 计算销售额和盈利能力指数：
   • 对于每个功能组合，遍历所有客户，检查该组合是否满足客户需求。如果满足，则增加销售额\(curSales\)和满足客户数量\(curCN\)。
   • 计算盈利能力指数\(curPI = curSales / curCost\)，并进行四舍五入处理。
   • 计算利润\(curPM = curSales - curCost\)。
4. 比较并更新最优解：
   • 根据题目给定的比较规则，比较当前组合与最优组合（\(maxPI\)、\(maxPM\)、\(minFN\)、\(maxCN\)等）。
   • 如果当前组合更优，则更新最优解的相关变量，包括\(bestState\)、\(maxPI\)、\(maxPM\)、\(minFN\)、\(maxCN\)、\(maxSales\)、\(maxExp\)以及\(cServerd\)数组。
5. 输出结果：
   • 按照输出格式要求，输出每个数据集的结果，包括盈利能力指数、总销售额、总开发成本、实现的功能列表以及满足的客户列表。

代码实现

/*
  利用位运算枚举
 */

#include <iostream>
#include <cmath>
#include <memory>
#include <climits> // 添加此头文件以引入 INT_MIN 和 INT_MAX
#define MAX_N 22
using namespace std;

int N, M;
int expV[MAX_N + 1];
double fCost[MAX_N + 1];  //从0开始

int cReq[MAX_N + 1][2]; //列：从0开始，行：0存数目，从1开始
double cAffor[MAX_N + 1]; //从0开始

int fNum, cNum, minFN, maxCN, bestState;
double minCost, maxCost, maxPI, maxPM, maxSales, maxExp; 

bool cServerd[MAX_N + 1];
bool cSAssit[MAX_N + 1];
void init()
{
	maxPI = maxPM = INT_MIN;
	minFN = INT_MAX;
}


int main()
{
	int i, j, k, caseN = 0, temp;
	for(i = 0; i <= MAX_N + 1; i++)
		expV[i] = pow(double(2), i);
	cin>>caseN;
	for(i = 1; i <= caseN; i++)
	{
		init();
		cin>>minCost>>maxCost>>fNum>>cNum;
		for(j = 0; j < fNum; j++)
			cin>>fCost[j];
		for(j = 0; j < cNum; j++)
		{
			cin>>cReq[j][0];
			int total = 0;
			for(k = 1; k <= cReq[j][0]; k++)
			{
				cin>>temp;
				total += expV[temp - 1];
			}
			cReq[j][1] = total;
			cin>>cAffor[j];
		}
		int curState;
		double curPI, curPM;
		int curFN, curCN;
		double curSales, curCost;
		for(curState = 0; curState <= expV[fNum] - 1; curState++)
		{
			if(curState == 57)
			{
				int a = 2;
			}
			curPI = curPM = curFN = curCN = curSales = curCost = 0;
			for(j = 0; j < fNum; j++)
				if(expV[j] & curState)
			{
				curFN++;
				curCost += fCost[j];
			}
			if(!(curCost >= minCost && curCost <= maxCost))
				continue;
			for(j = 0; j < cNum; j++)
			{
				int newVal = curState | cReq[j][1];
				if(newVal == curState)
				{
					curCN++;
					curSales += cAffor[j]; 
					cSAssit[j] = true;
				}
				else
					cSAssit[j] = false;
			}
			curPI = curSales / curCost;
			int tt = curPI * 10000 + 5;
			tt = tt / 10 * 10;
			curPI = double(tt) / double(10000);
			curPM = curSales - curCost;
			
			bool update = false;
			if(curPI > maxPI)
				update = true;
			else if(curPI == maxPI)
			{
				if(curPM > maxPM)
					update = true;
				else if(curPM == maxPM)
				{
					if(curFN < minFN)
						update = true;
					else if(curFN == minFN)
					{
						if(curCN > maxCN)
							update = true;
					}
				}
			}
			if(update)
			{
				bestState = curState;
				maxPI = curPI;
				maxPM = curPM;
				minFN = curFN;
				maxCN = curCN;
				maxSales = curSales;
				maxExp = curCost;
				for(j = 0; j < cNum; j++)
					cServerd[j] = cSAssit[j];
			}
		}
		cout<<"Feature Set "<<i<<endl;
		printf("%.3f\n", maxPI);
		printf("%.0f\n", maxSales);
		printf("%.0f\n", maxExp);
		
		bool v = false;
		for(j = 0; j < fNum; j++)
		{
			if(bestState & expV[j])
			{
				if(v)
					cout<<" ";
				else
					v = true;
				cout<<j + 1;
			}
		}
		cout<<endl;
		v = false;
		for(j = 0; j < cNum; j++)
		{
			if(cServerd[j])
			{
				if(v)
					cout<<" ";
				else
					v = true;
				cout<<j + 1;
			}
		}
		cout<<endl;
	}
	return 0;
}    

复杂度分析

1. 时间复杂度：
   • 枚举功能组合的时间复杂度为(O(2^N))，其中(N)是潜在功能数量。
   • 对于每个功能组合，检查客户需求的时间复杂度为(O(M))，其中(M)是潜在客户数量。
   • 因此，总的时间复杂度为(O(2^N \times M))。
2. 空间复杂度：
   • 主要的空间消耗在于存储功能开发成本、客户需求、满足客户列表等信息，空间复杂度为(O(N + M))。