Problem：
假定一段长度为i的钢条的价格为pi(I= 1, 2, …), 表格如下
|
长度i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
价格pi |
1 |
5 |
8 |
9 |
10 |
17 |
17 |
20 |
24 |
30 |
请问，给定一段长度为n的钢条和一个价格表pi如何切割，收益最大？
#include <string>
#include <iostream>
using namespace std;
int price_count = 10;
bool record[31] = {0};
int max_price(int *price, int length)
{
if (length == 1) return price[1];
if (length == 0) return 0;
int max = (length <= price_count && length >= 1) ? price[length] : 0;
if (record[length])
return price[length];
int temp = 0;
for (int i = 1; i < length; ++i)
{
temp = max_price(price, i) + max_price(price, length - i);
if (temp > max)
max = temp;
}
price[length] = max; //这步虽然越界，存在风险
//但是可以避免创建一个新的int数组
record[length] = 1;
return max;
}
/*
* max_price = max{max_price(i) + max_price(j)}
* 对特定长度进行递归，把已计算过的中间最大值进行存储指表，
* 便于下次递归使用
*/
int main(int argc, char const *argv[])
{
int price[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
for (int i = 20; i >= 8; --i)
cout << max_price(price, i) << endl;
return 0;
}
实际上，这是一种制表法，从1开始制最优值的表，
只不过是用递归来实现罢了，
所以有个风险，就是问题规模太大的话，可能出现段错误。
于是，可以把上述代码改写成一个迭代制表的程序。