你的位置:首页 > ASP.net教程

[ASP.net教程]算法导论


下班前看到有位兄弟写 钢条切割问题,尝试实现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;    }

 

结果: