算法導論-鋼條切割 C# 遞歸實現，

算法導論-鋼條切割 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;
        }

結果: