昨天在园子里看到朋友出的算法问题
http://www.cnblogs.com/eastjade/archive/2011/06/22/2086828.html
有一堆木棒长度在 1m - 21m之间（长度为整数），用户拥有的木棒长度也是用户自定义，的数量用户自定义 其中的一组样例数据是10m 的木棒 300跟， 14m 的木棒223跟， 18m 的木棒412跟， 2米的木棒301跟， 5米的木棒 48跟 我要求的是，这些木棒可以组成多少个 21米长的木棒？（木棒不可以切割，只可以拼接）。
原帖说这和买小鸡问题类似，其实不然，这比小鸡问题还要复杂一些。小鸡解决的是多少种组合的问题，而这个问题需要解决的是通过这些组合能产生多少根的问题。
本文的以每种组合消耗的木棒数最小为最做优原则，采用的穷举的算法，把每一堆木棒当成一个整体。每次从每一堆木棒里拿出一些木棒，由拿出的木棒组成一个小鸡问题，解决有多少种组合的问题，然后在可能的组合中寻找使用木棒数最小的组合，做为最优的方案，并把用到的木棒从相应的木堆中去除。重复这样的步骤，直到不能找出组合为至。
1. 新建表示一堆木头的类：
///
/// 一堆木头 /// public sealed class ManyMuTou { ///
/// 每根木头的长度 /// public int Value { get; private set; } ///
/// 木头的数量 /// public int Count { get; private set; } public ManyMuTou(int value, int count) { Value = value; Count = count; } ///
/// 当前能提供的木头数量 /// /// 组成的长度
///
public int CanGiveMuTou(int Sum) { var c = Sum / Value; return Math.Min(c, Count); } ///
/// 从木堆中移出木头 /// ///
public void UseMuTou(int count) { Count -= count; if (Count < 0) throw new Exception("没这么多了"); } }
2. 用于表示组合方案的类：
///
/// 组合方案 /// public sealed class ResultMuTou { ///
/// 组合的所有木棒 /// public List
Result; public ResultMuTou() { Result = new List(); } public ResultMuTou(ResultMuTou ru) { Result = new List(); foreach (var value in ru.Result) Result.Add(value); } /// /// 组合方案的总长度 /// public int Sum { get { return Result.Sum(); } } /// /// 添加一根长度为r的木棒 /// ///
public void Add(int r) { Result.Add(r); } /// /// 组合方案中木棒的数量 /// public int MouTouCount { get { return Result.Count; } } public override string ToString() { this.Result.Sort(); var s = ""; foreach(var value in Result) { if (s == "") s += value; else s += "+" + value; } return s; } }
3. 因为每次有多少个木堆都不是确定的，所有采用小鸡问题中的多重循环是行不通的，这里采用递归的方法 private List Computer(List MuTous,int Sum) { var ResultList = new List(); var lastCount = ResultList.Count - 1; int level = 0; while (lastCount != ResultList.Count) { lastCount = ResultList.Count; var tempresultlist = new List(); for (int i = 0; i <=MuTous[level].CanGiveMuTou(Sum); i++) { ResultMuTou rmt = new ResultMuTou(); for (int j = 0; j 0) { var Su = tempresultlist.First(s => s.MouTouCount == tempresultlist.Min(t => t.MouTouCount)); ResultList.Add(Su); foreach (var value in Su.Result) { MuTous.First(t => t.Value == value).UseMuTou(1); } } } return ResultList; } private void GetReuslt(List MuTous, ResultMuTou rmt, int Sum, int level, List tempresultlist) { if (rmt.Sum == Sum) { tempresultlist.Add(rmt); return; } if (level >= MuTous.Count) { return; } for (int i = 0; i <=MuTous[level].CanGiveMuTou(Sum); i++) { var Rmt = new ResultMuTou(rmt); for (int j = 0; j < i; j++) Rmt.Add(MuTous[level].Value); GetReuslt(MuTous, Rmt, Sum, level + 1, tempresultlist); } }
4. 最后测试样例子数据：
var MuTous = new List(); MuTous.Add(new ManyMuTou(10, 300)); MuTous.Add(new ManyMuTou(14, 223)); MuTous.Add(new ManyMuTou(18, 412)); MuTous.Add(new ManyMuTou(2, 301)); MuTous.Add(new ManyMuTou(5, 48));
List ResultList = Computer(MuTous,21); Debug.WriteLine(ResultList.Count); foreach (var l in ResultList) Debug.WriteLine(l);
结果如下：
48 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14 2+5+14
延伸阅读
最新评论