首页 > 代码库 > 算法：木材等分
算法：木材等分
题目：
有N（N=3）根木材，长度分别为A，B，C（A=8.0，B=10.0，C=100.0），分为长度相同的X（X=100）单份。求单份最大的长度。
分析：
N根木材，等分为X份。最优解是 AVG = (A+B+C)/X。实际情况中，每根木材可能有剩余，这样就得不到X份。
既然得不到X份，那就反推。COUNT = A/AVG + B/AVG + C/AVG。除法计算向下取整。X-N < COUNT <=X。
原因是 (Ma*AVG+Da) + (Mb*AVG+Db) +(Mc*AVG+Dc) = X*AVG。（A以AVG长度分成Ma份，剩余Da，类推。）0 <=Da <AVG。
先判断 Ma+Mb+Mc 的值，如果小于X，将A分为（Ma+1）份，即La1 = A/(Ma+1)。分为（Ma+2）份，La2 = A/(Ma+2)。直到分为（Ma+N-1）份，Lax = A/(Ma+N-1)。
依次类推B分为Mb份。。。
将La1, La2 ... Lb1, Lb2,... 按大到小的顺序排列，计算 (A/L + B/L + C/L)的值，如果大于或等于X，则L即为所求。
程序：
private static bool DevideInCommon(double[] arrLength, int intCount){ //判断存在负数或0 if (arrLength.Any(i => i <= 0)) { return false; } int intNum = arrLength.Length; double maxAVG = arrLength.Sum() / intCount; int[] arrCount = arrLength.Select(i => Convert.ToInt32(Math.Floor(i / maxAVG))).ToArray(); if (arrCount.Sum() < intCount) { List<double> lstLength = new List<double>(); for (int i = 0; i < arrLength.Length; i++) { for (int j = 1; j < intNum; j++) { double tmpL = arrLength[i] / (arrCount[i] + j); int[] arrCount2 = arrLength.Select(m => Convert.ToInt32(Math.Floor(m / tmpL))).ToArray(); if (arrCount2.Sum() < intCount) { continue; } else { lstLength.Add(tmpL); break; } } } double intResult = lstLength.Max(); Display(arrLength, intResult); } else { Display(arrLength, maxAVG); } return true;}
辅助显示
private static void Display(double[] arrLength, double avgLength){ Console.WriteLine("AVG: " + avgLength); foreach (double len in arrLength) { Console.WriteLine("Length: " + len + " Count: " + Math.Floor(len / avgLength)); }}
希望对你有帮助。
算法：木材等分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。