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