动态规划解决钢条切割问题代码,C代码库,德仔网

代码语言

代码分类

【C】动态规划解决钢条切割问题

作者:weinee / 发布于2015/4/8/ 616

给定一段长度为 n 的钢条和一个价格表 pi(i=1,2,…,n)，求切割钢条方案，
使得销售收益 rn最大。
提示：要求长度为 n 的钢条的最好切割方案，可以使用以下递归求解方法：
将钢条从左边切割下来长度为 i 的一段，对右边剩下长度为 n-i 的一段继续进行
切割（递归求解），对左边一段不再进行切割。


	#include <iostream>
	
	/*
	* 钢条切割问题
	* parameter: p[i]为长度为i的钢条的价格，n为钢条的长度。
	*/
	int gtqg(int p[], int n){
	 int *r;
	 r = new int[n + 1];
	 r[0] = 0;
	 for (int i = 1; i <= n; i++){
	 r[i] = 0;
	 for (int j = 0; j < i; j++){
	 if (r[i] < p[j] + r[i - j - 1]){
	 r[i] = p[j] + r[i - j - 1];
	 }
	 }
	 }
	 return r[n];
	}
	
	int main(int argc, char** argv) {
	 int p[] = { 1, 3, 7, 8, 9, 11 };
	 int m = gtqg(p, 6);
	 printf("%d\n", m);
	 return 0;
	}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　钢条切割　

同语言下

可能有用的

weinee贡献的其它代码(4)