TopCoder SRM324 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=6811&rd=10004
给出n种商品不同顾客的购买选择,计算打包组合的商品,即所有顾客要么都买要么都不买的组合,返回最小的打包数。
最直接的想法就是遍历一边,每个顾客的数据分成不断对当前的各个包取交和取减分为更小的包
可是这样的复杂度高达2的N次方,以案例的数据量50来看一定是超时的
答案是将输入从不同顾客的产品选择转化成为不同产品的购买顾客
结果是直接比较两种产品的就可以知道是否可以在同一个包中
大大降低的复杂度
只要能相通这一点
后面的代码是非常容易的