问题描述
解题思路：我们可以进行划分为更小的子问题，钢条的最大收益就是分为两种情况，一是钢条不要切割时能够获得最大收益，另一种时钢条要切割时获得最大收益，对于要切割的钢条我们又可以进行切割与不切割的讨论。
除了上面解法，钢条还可以从左边切割下长度为i的一段，所以右边就只剩下Len-i的长度了，就只对右边进行切割(递归求解),左边就不再切割。所以为题分解为左边一段（不管）和剩余右边一段继续切割的结果
自顶向下
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn =
100;
int p[maxn];
int num, l;
int cut(
int *p,
int n,
int *r)
{
int q;
if (r[n] >=
0)
return r[n];
if (n ==
0)
q =
0;
else
{
q = -(
1 <<
20);
for (
int i =
1; i <= n; i++)
{
q = max(q,p[i]+cut(p, n - i, r));
}
}
r[n] = q;
return q;
}
int M(
int *p,
int n)
{
int r[maxn];
for (
int i =
0; i <= n; i++)
r[i] = -(
1 <<
20);
return cut(p, n, r);
}
int main()
{
int p[
11] = {
0,
1,
5,
8,
9,
10,
17,
17,
20,
24,
30 };
for(
int i=
1;i<=
10;i++)
cout << M(p,i)<<endl;
system(
"pause");
return 0;
}
自底向上 打印路径
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn =
100;
int p[maxn];
int s[maxn];
int num, l;
int FindCut(
int *p,
int n)
{
int q;
int r[maxn] ;
r[
0] =
0;
for (
int i =
1; i <= n; i++)
{
q = -(
1 <<
20);
for (
int j =
1; j <= i; j++)
{
if (q <p[j] + r[i - j])
{
q = p[j] + r[i - j];
s[i] = j;
}
}
r[i] = q;
}
return r[n];
}
int main()
{
int p[
11] = {
0,
1,
5,
8,
9,
10,
17,
17,
20,
24,
30 };
cout << FindCut(p,
9)<<endl;
int n=
9;
while (n >
0)
{
cout << s[n]<<
" ";
n = n - s[n];
}
system(
"pause");
return 0;
}
