依原题意，设共有N件商品，M种套餐。
标准解法：
1、 所需数据结构：
private static Set<Integer> items;
private static ArrayList<Set<Integer>> groups;
private static HashMap<Set<Integer>,ArrayList<Integer>> status;
2、 数据结构说明：
items： 存储购买的商品id，为集合类型
groups：存储套餐，每种套餐以集合类型存储
status：存储所有可能的解及对应的套餐组合，每一个key为一个可行解，每一个value为对应当前解的套餐组合（即到达当前组合的路径）
3、 解题核心思路：
若存在某种套餐组合使物品集setA={a,b,c,d}成立，那么若有套餐setB={e,f}，那么：
setX = setA+setB = {a,b,c,d,e,f}
也必将成立（每一个可能状态都可以由且只能由其他状态"转移"而来）。
4、 解题步骤：
1. 初始化一个空解set={}, 放入status中；
2. 遍历每一个套餐group_i:
3. 遍历每一个可行解status_i:
4. 若group_i与status_i的交集为空，则求并集生成新解，并存入status中；
//新解的套餐组合为status_i所对应的套餐组合+group_i对应的套餐
5. 遍历status中的所有可行解，求出size()最大的集合，即为最优解；
5、 一些简单有效的优化：
1. 若某商品在所有套餐中都不存在，则可剔除
2. 若某套餐中包含未购买的商品，则可剔除
3. 若某套餐可由两个或多个套餐相加而成，则可剔除
4. 通过并查集算法，若能将套餐分成互不关联的组合，则可分组求解后再归并求和
5. 可在解题步骤第4步中把当前最优的方案存储下来，如此可省去第5步的再次遍历操作
6. 状态压缩（假设购买的商品总数<=32个）：
本题中物品的状态组合非常多(2^n)，但每一个物品的可能状态较少（只有被选与不被选两种，即0和1），所有可以考虑用2进制表示这些状态。
例如，当某套餐X包含商品A4,A3,A1，则可表示成1101（二进制），当某套餐Y包含商品A6,A2，则可表示成100010（二进制）。同时选了这两个套餐的一个状态则可表示成101111（二进制）。
于是，原数据结构中存储套餐和状态的Set<Integer>均可简化成Integer，即：
private static ArrayList<Integer> groups;
private static HashMap<Integer,ArrayList<Integer>> status;
如此处理之后，原集合间的计算（交集、并集、差集等）均可简化为两个整数间的位操作，计算复杂度由O(n)降低至O(1)。
6、 时间复杂度的证明：
1. 所有商品都只有取或不取两种状态，所以status的总状态数不会超过2^n；
2. 每个套餐遍历完后，status的size()最多扩大一倍，所以status的总状态数不会超过2^m；
3. 所以总时间复杂度为O(2^min(n,m))
关于此题的一些延伸思考：
原题中为满足套餐的物品组打九折，即每件商品的权重相等。若是每个套餐给出总售价，求总价最低的套餐组合呢？即每一个套餐的"key"依然是物品组，"value"不再是商品的个数而是一个具体的值，即每一个套餐可表示成：
| 套餐ID | 商品ID组 | 总价$ |
|---|---|---|
| G1 | A1,A2,A3,A4,A5,A6 | 1600 |
| G2 | A1,A2,A50 | 1200 |
如此，其实只需对原先的核心解题思路稍作修改即可：
原：
若存在某种套餐组合使物品集setA={a,b,c,d}成立，那么若有套餐setB={e,f}，那么：
setX = setA+setB = {a,b,c,d,e,f}
也必将成立。
修改成：
若存在某种套餐组合使物品集setA={a,b,c,d}的最低打包价为valueA，若有套餐setB={e,f}的打包价为valueB，设setX={a,b,c,d,e,f}且最低打包价为valueX（初始化为无穷大），那么：
setX = min{ valueA+valueB , valueX }
即每一个状态是当前套餐组下的最优策略（最低的总价）。
所需的数据结构如下：
//下标表示商品id，Double表示对应商品的单价
private static ArrayList<Double> items;
//每一个Entry表示一个套餐，Entry中的key(Integer)表示商品的选取状态(已用状态压缩过的二进制表示),value(Double)表示该套餐的总价
private static ArrayList<Entry<Integer, Double>> groups;
//HashMap中的每一个值表示一个可行解。每一个可行解中的key(HashMap<Integer, Double>)表示该解对应的商品选取状态(同样已用二进制表示)及最低总价，value(ArrayList<Integer>)表示对应的套餐组。
private static HashMap<HashMap<Integer, Double>,ArrayList<Integer>> status;
如此处理后，在计算完所有的可能状态后，遍历所有状态并求其与未在套餐组里商品的原价之总和，最低的总价即为最优解。
网友评论