今天用了递归来解决昨天钢管的最有切割问题，代码如下

#include <iostream>

#include <algorithm>

#include <time.h>

using namespace std;

int cut_rod(int *p, int n);

int p[1000];

int main()

{

clock_t start, finish;

double duration = 0.0;

memset(p, 0, sizeof(p));

p[0]=0;

p[1]=1;

p[2]=5;

p[3]=8;

p[4]=9;

p[5]=10;

p[6]=17;

p[7]=17;

p[8]=20;

p[9]=24;

p[10]=30;

int q = 0， n = 0; //q为最大价格，n为钢材长度，p数组为价格目录

cout << "请输入钢材的长度：";

cin >> n;

start = clock();

q = cut_rod(p, n);

cout << "最大收益为 "<< q << endl;

finish = clock();

duration = (double)(finish - start)/CLOCKS_PER_SEC;

cout << "it takes "<< duration << "seconds" <<endl;

return 0;

}

int cut_rod(int *p, int n)

{

int q = -1e8;

if (n == 0)

{

return 0;

}

else

{

for(int i = 1; i <= n; i++)

{

q = max(q, p[i] + cut_rod(p, n-i));

}

}

return q;

}

 

如果各位有好的计算时间的函数，或给数组前几个元素赋值而使后面全为0的函数麻烦告知下，哪里有写的不好的地方请指正。

这个算法的时间复杂度很高，远没有前面那个算法好，当n=30是计算时间达到了2分多钟，前面那个只要0.00000秒、、、、贴图如下，正在学习改进方法