seki & 竹间智能

依原题意，设共有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;

如此处理后，在计算完所有的可能状态后，遍历所有状态并求其与未在套餐组里商品的原价之总和，最低的总价即为最优解。