※ 引述《ssccg (23)》之銘言： : ※ 引述《dlikeayu (太陽拳vs野球拳)》之銘言： : : 作者: dlikeayu (太陽拳vs野球拳) 看板: Prob_Solve : : 標題: [問題] 不重覆的排列組合 : : 時間: Thu Jun 7 19:55:22 2012 : : 有個問題想要請較大家 : : 我有兩組SET : : 甲 {A,B,C}優先權低 : : 乙{A,D,E}優先權高 : : 然後我有一串值 : : {B,C,E,B,A,D,E} : : 我要從中選出來 : : 甲或乙各有幾組 : : 被選走的就不能再被用 : : 所以要是乙跟甲都能組合的話 : : 乙會優先抽走 : : 因為值很少 : : 可以自己算出 : : 甲 0 組 : : 乙 1 組 : : 剩BBCE : : 請問用算的這種有什麼演算法能適用解決呢？ : → ssccg:既然有優先順序，不就算出最多能抽幾組乙，減掉這數量再算 06/07 20:13 : → ssccg:最多幾組甲就好了? 06/07 20:13 : : 如果這是個function ，那要怎麼知道有幾組乙(不重覆)，asp.net的方法我不太熟 : : 然後去執行交集運算C#(剛從數學版得到的資訊 )幾次 : : http://msdn.microsoft.com/zh-tw/library/system.linq.enumerable.except.aspx : : 又集合了幾個網友的資訊 : : C# ASP.NET 有 counting sort的函式可用嗎？ : : 先排出優先權最高的set放進一List或array : : 然後再counting sort知道有n組 乙set : : 差集運算 n 次 : : 下一個set : : loop : 如果你只是要算數量 : 其實不需要管set，直接根據數量統計就好了 : 先統計各個值可被取的數量 : 然後依優先順序對每個set找出該set包含的值哪個的可取數量最少 : 這個數量就是set最大組數 : 把可取數量有被取走的值都減掉這個組數再算下一個set : 就可以得到所有set的組數了 : 以下假設值是string: : // 依優先權排好的set : HashSet<string>[] setQueue = { 乙, 甲, ... }; : // 一串值 : string[] valuePool = {"B","C","E", ...}; : // 結果 : int[] result = new int[setQueue.Length]; : Dictionary<string,int> valueCounts = valuePool.GroupBy(v => v) : .ToDictionary(g => g.Key, g => g.Count()); : for(int i = 0; i < setQueue.Length; ++i) : { : result[i] = setQueue[i].Min(val => : valueCounts.Keys.Contains(val) ? valueCounts[val] : 0 : ); : if(result[i] > 0) : foreach (string val in setQueue[i]) : valueCounts[val] -= result[i]; : } 謝謝 後來延伸個更可怕的問題 甲乙或是可能多丙丁組合 然後優先權還有"級別數" 這邊開始就變可怕了… 假設 (數字愈小愈高) 甲 =1 乙 =2 丙 =3 丁 =1 這樣變成要從一組數裏面 先去排列出各種可能 然後再算出總合級數是最小的配法 要是今天一個比對值裏有一堆 A,B,B,C,D,D,D,A,E,F,G,E,F,H(或更常符合更多組甲~庚) 這樣程式是不是會算到死啊... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.61.247.2