TopCoder SRM324 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=6811&rd=10004
給出n種商品不同顧客的購買選擇,計算打包組合的商品,即所有顧客要么都買要么都不買的組合,返回最小的打包數。
最直接的想法就是遍歷一邊,每個顧客的數據分成不斷對當前的各個包取交和取減分為更小的包
可是這樣的復雜度高達2的N次方,以案例的數據量50來看一定是超時的
答案是將輸入從不同顧客的產品選擇轉化成為不同產品的購買顧客
結果是直接比較兩種產品的就可以知道是否可以在同一個包中
大大降低的復雜度
只要能相通這一點
后面的代碼是非常容易的
http://www.topcoder.com/stat?c=problem_statement&pm=6811&rd=10004
給出n種商品不同顧客的購買選擇,計算打包組合的商品,即所有顧客要么都買要么都不買的組合,返回最小的打包數。
最直接的想法就是遍歷一邊,每個顧客的數據分成不斷對當前的各個包取交和取減分為更小的包
可是這樣的復雜度高達2的N次方,以案例的數據量50來看一定是超時的
答案是將輸入從不同顧客的產品選擇轉化成為不同產品的購買顧客
結果是直接比較兩種產品的就可以知道是否可以在同一個包中
大大降低的復雜度
只要能相通這一點
后面的代碼是非常容易的