※ 引述《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