题目描述

Cash Cow咨询公司正在挑战各位副总裁，要求他们提升各自部门的盈利能力。为了激励大家，公司决定将一辆全新的保时捷奖励给“盈利能力指数”（Profitability Index，简称PI）最高的部门副总裁。比赛规则如下：

1. 获胜部门需满足其盈利能力指数（销售额 / 开发成本）最大。
2. 每个部门的开发成本必须控制在给定的最小值和最大值范围内。
3. 如果两个部门的盈利能力指数相同（四舍五入到三位小数后相等），则选择利润更高（销售额 - 开发成本）的部门。
4. 若仍相同，选择开发功能数量更少的部门。
5. 若仍相同，选择满足客户数量更多的部门。

Mike Miser目前还骑着他的高中时代的小摩托，决心抓住这次机会升级座驾。他要求工程部计算每个功能的开发成本，并让销售团队统计每位客户的需求及其带来的销售额。注意：要赢得客户订单，必须实现该客户要求的所有功能。

输入说明

所有输入均为正整数。

• 第一行为数据集的数量。
• 每个数据集的第一行包含四个整数，分别表示：最小成本、最大成本、潜在功能数量$（N ≤ 20）$、潜在客户数量$（M ≤ 20）$。
• 接下来的$N$行，每行给出一个功能的开发成本。
• 接下来的$M$行，每行描述一个客户的需求：
  • 格式为：所需功能数量 功能编号列表 销售额
  • 例如：3 1 2 5 50 表示该客户需要功能1、2、5，销售额为50。

输出说明

每个数据集的输出格式如下：

1. 第一行：Feature Set N（N从1开始）。
2. 第二行：盈利能力指数（保留三位小数）。
3. 第三行：总销售额。
4. 第四行：总开发成本。
5. 第五行：实现的功能列表（按编号升序排列，空格分隔）。
6. 第六行：满足的客户列表（按编号升序排列，空格分隔）。

1  
100 2000 7 6  
250  
350  
400  
250  
250  
250  
500  
4 1 4 5 6 4000  
4 1 4 5 6 500  
4 1 4 5 6 60  
3 1 4 5 7  
4 1 2 3 5 5  
4 1 2 3 7 6   

Feature Set 1  
4.567  
4567  
1000  
1 4 5 6  
1 2 3 4  

注意事项

1. 生产成本可忽略，仅考虑开发成本。
2. 题目保证通过比较规则能唯一确定获胜部门。
3. 至少有一个功能组合满足成本范围要求。
4. 盈利能力指数比较时，四舍五入到三位小数（例如3.4566和3.4574视为相等）。

题目来源：Mid-Atlantic 2001