算法导论-钢条切割 C# 递归实现

下班前看到有位兄弟写 钢条切割问题，尝试实现C#版， 还没有实现最优版，分享一下。

int[] parr; PRivate void button1_Click(object sender, EventArgs e)        {            //策略标准，如 总长度 7 取第1位，6位 , 最优结果是:  18 = 1 + 17             parr = new int[] {                 1 , 5 , 8 , 9 , 10 , 17 , 17 , 20 , 45 , 30            };            Stack<int> stack = new Stack<int>();            //总容量            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("结果:{0}", result);        }

核心部分:

  /// <summary>        ///         /// </summary>        /// <param name="p">策略标准</param>        /// <param name="length">分割集合</param>        /// <param name="stack">分割步骤</param>        /// <returns></returns>        int compute(int[] p, int length, ref  Stack<int> stack)        {            int price = 0;            //最优方案            int maxPrice = 0;            //截止目前 本轮最优方案步骤            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);                    //更新本轮最优方案                    __stack = _stackTemp;                }            }            //将本轮最优方案添加到全局方案集            while (__stack.Count > 0) {                stack.Push(__stack.Pop());            }                        //返回最优结果            return maxPrice;        }

结果: