下班前看到有位兄弟寫 鋼條切割問題，嘗試實現(xiàn)C#版， 還沒有實現(xiàn)最優(yōu)版，分享一下。

int[] parr; PRivate void button1_Click(object sender, EventArgs e)        {            //策略標(biāo)準(zhǔn)，如 總長度 7 取第1位，6位 , 最優(yōu)結(jié)果是:  18 = 1 + 17             parr = new int[] {                 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 , 45 , 30            };            Stack<int> stack = new Stack<int>();            //總?cè)萘?           int maxLength = 7 ;            int result = compute(parr, maxLength, ref stack);            int c = stack.Count;            Console.WriteLine("切割:");            int temp;            while (c-- > 0) {                Console.WriteLine(temp = stack.Pop());            }                      Console.WriteLine("結(jié)果:{0}", result);        }

核心部分:

  /// <summary>        ///         /// </summary>        /// <param name="p">策略標(biāo)準(zhǔn)</param>        /// <param name="length">分割集合</param>        /// <param name="stack">分割步驟</param>        /// <returns></returns>        int compute(int[] p, int length, ref  Stack<int> stack)        {            int price = 0;            //最優(yōu)方案            int maxPrice = 0;            //截止目前 本輪最優(yōu)方案步驟            Stack<int> __stack = null;            //臨時方案步驟            Stack<int> _stackTemp = null  ;            int split;            if (length == 0)                return 0;            for (int i = 1; i <= length ; i++ )            {                if (i >= p.Length)                {                    split = p.Length;                                    }                else                {                    split = i;                }                //臨時方案                _stackTemp = new Stack<int>();                price = p[split - 1] + compute(p, length - split, ref _stackTemp);                                if (maxPrice < price)                {                    //新方案                    maxPrice = price;                    _stackTemp.Push(split);                    //更新本輪最優(yōu)方案                    __stack = _stackTemp;                }            }            //將本輪最優(yōu)方案添加到全局方案集            while (__stack.Count > 0) {                stack.Push(__stack.Pop());            }                        //返回最優(yōu)結(jié)果            return maxPrice;        }

結(jié)果: