《算法导论》学习（十七）----动态规划之钢条切割（C语言）

---

前言

本文主要讲解了钢条切割问题的解决方案，并且给出了C语言代码。其中涉及到了动态规划的思想，会在之后的文章中详细讲解

---

一、钢条切割问题

1.问题背景

Serling公司购买长钢条，将其切割成短钢条进行出售。切割工序本身没有成本支出。管理层希望得到最优的切割方法。
现在我们知道Serling公司出售一段长度为$i$英寸的钢条的价格为$p_i(i=1,2,3,...,n)$，单位为美元。钢条的长度都为整英寸。

举例一个价格的样表如下：

2.问题描述

现在我们的问题是：

给定一段长度为$n英寸$的钢条和一个价格表$p_i(i=1,2,...,n)$，求切割钢条的方案，使得收益$q$最大化。

3.问题的难点

（1）情况较多

首先我们有如下结论：
$$长度为n英寸的钢条共有2^{n-1}种不同的切割方案$$
具体的分析如下：

• 对于长度为n英寸的钢条，我们有n-1个可切割点
• 那么每个切割点的情况分为两种：切断或者不切断
• 有n-1个点，每个点有两种情况

综上所述：总情况为$2^{n-1}$

（2）消除重复子问题

我们可以试想以下，当我们想知道长度为7的钢条如何切割，会需要先解决一部分子问题，记为集合A。
而我们要解决长度为5英寸的钢条的子问题集为B
那么A与B肯定存在公共的子问题需要求解

那么这样看来，解决长度越长，包含更多的重复的子问题来浪费资源。

二、问题解决方案

1.问题的特点

（1）最优化子结构

首先该问题是求解一个最优化的问题。

其次我们可以将该最优化问题分解为诸多最优化的子问题来求解
举个例子
对于长度为4的问题，我们可以这样分割：
$$4的最优解=最优（1的价格+3的最优，2价格+2的最优，3的价格+1的最优<1的最优也便是1的价格>）$$
可以发现该最优问题确实可以分解为诸多最优子问题来解决。
涉及到了子问题，这样我们就顺其自然地用递归等方法来解决问题。

（2）重复子问题

这里前文已经分析过。会有资源耗费在解决重复的子问题上。
那么我们需要想方案让这些子问题仅解决一次，这里就用到了动态规划的思想。
我们有两种具体的方案：

• 带备忘的自顶向下
• 自底向上

下文将进行具体讲解

2.最优化解决方案

（1）自顶向下的普通递归

该方案就是编程实现上文中将问题分解为子问题的过程。
采用递归的方式，遍历所有的情况。
最后时间复杂度将是可怕的$O(2^n)$

（2）带备忘的自顶向下

该方案对比普通的自顶向上的方案仅有一个改进之处
就是采用一个存储数组存储已经解决的子问题，如果下次遇到已经解决过的子问题，那么直接在存储数组中查找即可，节省了时间

（3）自底向上

该方案是先从最底层的子问题开始解决，接着向上一层解决高一层的子问题。
以此不断循环，最后将总体问题解决。

3.构建最优解的结构

我们现在得到了最大利润，但是如何得到最优的方案呢？
我们需要引入一个存储数组s，存储“切割的第一刀”

现在我们来理解什么是“切割的第一刀”，回想以下我们如何将长度4的问题进行切割的：
$$4的最优解=最优（1的价格+3的最优，2价格+2的最优，3的价格+1的最优<1的最优也便是1的价格>）$$
对于上述的例子来说，可能的“切割的第一刀”有：1，2，3。
我们可以理解为，切割这个第一刀后，问题被分解为最优子问题。
因此我们需要存储所有问题的”第一刀“，然后就可以通过一个简单的循环找到具体的切割方案。

三、C语言代码

1.三种方案的函数代码

（1）自顶向下的普通递归

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自顶向下不加备忘机制
int CUT_ROD(int *p,int n,int size)
{
	int q=0;
	int i=0;
	if(n==0)
	{
		return 0;
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}	
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}
	}
	return q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

（2）带备忘的自顶向下

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自顶向下加备忘机制方法
int MEMORIZED_CUT_ROD_DO(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	int i=0;
	if(w[n]>=0)
	{
		return w[n];
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}		
	}
	w[n]=q;
	return q;
}
int MEMORIZED_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int i=0;
	for(i=0;i<=n;i++)
	{
		w[i]=-1;
	}
	w[0]=0;
	s[0]=0;
	return MEMORIZED_CUT_ROD_DO(p,n,w,s,size);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

（3）自底向上

//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 
//自底向上的方法
int BOTTOM_UP_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	w[0]=0;
	s[0]=0;
	int j=0;
	int i=0;
	for(j=1;j<=n;j++)
	{
		q=-10;
		if(j>=size)
		{
			for(i=1;i<size;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		else
		{
			for(i=1;i<=j;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		w[j]=q;
	}
	return w[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

2.整体测试代码

#include
#include
#include


 
//由于要存放长度为0时，钢条的价格为0 
//因此市场上可以出售钢条长度为1~SIZE-1
//这SIZE-1种整数长度
//比如SIZE=5时
//钢条可以切成1，2，3，4 
#define SIZE 6//输入规模 

//钢条长度每增加一单位 
//其价格增加LIM+1
//因此它是钢条价格的单位随机增量 
#define LIM 7//随机数的范围：0~(LIM-1)

//钢条的总长度 
#define Length 10; 



//返回最大值函数
int MAX(int a,int b)
{
	if(a>=b)
	{
		return a;
	}
	else
	{
		return b;
	}
} 



//自顶向下不加备忘机制
int CUT_ROD(int *p,int n,int size)
{
	int q=0;
	int i=0;
	if(n==0)
	{
		return 0;
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}	
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			q=MAX(q,p[i]+CUT_ROD(p,n-i,size));
		}
	}
	return q;
} 



//自顶向下加备忘机制方法
int MEMORIZED_CUT_ROD_DO(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	int i=0;
	if(w[n]>=0)
	{
		return w[n];
	}
	q=-10;
	if(n>=size)
	{
		for(i=1;i<size;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			if(q<(p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size)))
			{
				s[n]=i;
				q=p[i]+MEMORIZED_CUT_ROD_DO(p,n-i,w,s,size);
			}			
		}		
	}
	w[n]=q;
	return q;
}
int MEMORIZED_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int i=0;
	for(i=0;i<=n;i++)
	{
		w[i]=-1;
	}
	w[0]=0;
	s[0]=0;
	return MEMORIZED_CUT_ROD_DO(p,n,w,s,size);
}




//自底向上的方法
int BOTTOM_UP_CUT_ROD(int *p,int n,int *w,int *s,int size)
{
	int q=0;
	w[0]=0;
	s[0]=0;
	int j=0;
	int i=0;
	for(j=1;j<=n;j++)
	{
		q=-10;
		if(j>=size)
		{
			for(i=1;i<size;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		else
		{
			for(i=1;i<=j;i++)
			{
				if(q<(p[i]+w[j-i]))
				{
					s[j]=i;
					q=p[i]+w[j-i];
				}
			}			
		}
		w[j]=q;
	}
	return w[n];
}



//打印钢条的最优组合
void print_max(int *s,int n)
{
	int i=n-1;
	printf("价格最优情况下，钢条的长度组合之一如下：\n"); 
	while(i>0)
	{
		printf("%5d",s[i]);
		i=i-s[i];
	}
	printf("\n");
} 



//主函数
int main()
{
	int i=0;
	int maxp=0;
	int n=Length; 
	int p[SIZE];
	int w[n+1];
	int s[n+1];
	srand((unsigned)time(NULL));
	int temp=0;
	for(i=0;i<SIZE;i++)
	{
		p[i]=temp;
		temp=temp+rand()%LIM+1;
	}
	for(i=0;i<SIZE;i++)
	{
		printf("%5d",p[i]);
	}
	printf("\n");
	//自顶向下不加备忘机制
	maxp=CUT_ROD(p,n,SIZE);
	printf("max profit is %5d\n",maxp);
	//自顶向下加备忘机制方法
	maxp=MEMORIZED_CUT_ROD(p,n,w,s,SIZE);
	printf("max profit is %5d\n",maxp);
	print_max(s,n+1);
	//自底向上的方法
	maxp=BOTTOM_UP_CUT_ROD(p,n,w,s,SIZE);
	printf("max profit is %5d\n",maxp);
	for(i=0;i<=n;i++)
	{
		printf("%5d",w[i]);
	}
	printf("\n");
	print_max(s,n+1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

---

总结

文章不妥之处请各位读者包涵指正