昨天在园子里看到朋友出的算法问题

  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. 新建表示一堆木头的类：

  /// <summary>
    /// 一堆木头
    /// </summary>
    public sealed class ManyMuTou
    {
        /// <summary>
        /// 每根木头的长度
        /// </summary>
        public int Value { get; private set; } 

        /// <summary>
        /// 木头的数量
        /// </summary>
        public int Count { get; private set; }


        public ManyMuTou(int value, int count)
        {
            Value = value;
            Count = count;
        }

        /// <summary>
        /// 当前能提供的木头数量
        /// </summary>
        /// <param name="Sum">组成的长度</param>
        /// <returns></returns>
        public int CanGiveMuTou(int Sum)
        {
            var c = Sum / Value;
            return Math.Min(c, Count);
        }

        /// <summary>
        /// 从木堆中移出木头
        /// </summary>
        /// <param name="count"></param>
        public void UseMuTou(int count)
        {
            Count -= count;
            if (Count < 0)
                throw new Exception("没这么多了");
        }
    }

2. 用于表示组合方案的类：

  /// <summary>
    /// 组合方案
    /// </summary>
    public sealed class ResultMuTou
    {
        /// <summary>
        /// 组合的所有木棒
        /// </summary>
        public List<int> Result;

        public ResultMuTou()
        {
            Result = new List<int>();
        }

        public ResultMuTou(ResultMuTou ru) 
        {
            Result = new List<int>();
            foreach (var value in ru.Result)
                Result.Add(value);
        }

        /// <summary>
        /// 组合方案的总长度
        /// </summary>
        public int Sum { get { return Result.Sum(); } }

        /// <summary>
        /// 添加一根长度为r的木棒
        /// </summary>
        /// <param name="r"></param>
        public void Add(int r)
        {
            Result.Add(r);
        }

        /// <summary>
        /// 组合方案中木棒的数量
        /// </summary>
        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<ResultMuTou> Computer(List<ManyMuTou> MuTous,int Sum)
        {
            var ResultList = new List<ResultMuTou>();
            var lastCount = ResultList.Count - 1; 
            int level = 0;

            while (lastCount != ResultList.Count)
            {
                lastCount = ResultList.Count;
                var tempresultlist = new List<ResultMuTou>();
                for (int i = 0; i <=MuTous[level].CanGiveMuTou(Sum); i++)
                {
                    ResultMuTou rmt = new ResultMuTou();
                    for (int j = 0; j <i; j++)
                        rmt.Add(MuTous[level].Value);

                    GetReuslt(MuTous, rmt, Sum, level+1, tempresultlist);
                }
                if (tempresultlist.Count > 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<ManyMuTou> MuTous, ResultMuTou rmt, int Sum, int level, List<ResultMuTou> 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<ManyMuTou>();
            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<ResultMuTou> 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

 


作者: 张亚 发表于 2011-06-23 09:44 原文链接

Tag 木头问题的穷举算法
推荐.NET配套的通用数据层ORM框架：CYQ.Data 通用数据层框架