Posted on 2012-01-29 20:40
Seed-L 阅读(2620)
评论(0) 编辑 收藏 引用
1
图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。(自己外加一个条件，还要找出最大路的路径，并打印出来)
2
3
4
5注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
6
7Input
8
9输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
10
11Output
12
13输出最大的和。
14
15Sample Input
16
17
185
197
203 8
218 1 0
222 7 4 4
234 5 2 6 5
24
25
26
27Sample Output
28
297
30
313
32
338
34
352
36
375
38
3930
40
41
42
43
44
45
46
/**//* -------------------------------------------------------------------------------------------
47
Test.cpp
48 说明：用动态规划法来做，不过，不知道我这一种算不算.
49 (PS:没有到任何ACM online judge上面测试过，所以有错误欢迎指出)
50
51
52 动态规划法（我的大概想法）：
53 1、描述通往最大值的路径的结构（描述最优解的的结构的特征）
54
55 通过最后一层的某个结点a[i][j]就是最大值路径和的最后一个结点。那么通过
56 最大值路径的最后一个结点a[i][j]时，通过a[i-1][*](*为j-1或j)的结点的路
57 径必然也是最大值的。如果有通过另外的结点a[i-1][.]的路径和比通过a[i][*]
58 的路径和要大，即产生矛盾.
59
60
61 2、递归定义最优解的值(一个递归的解)
62
63
64 根据1的结论得
65
66 [ a[i] i = 0
67 RouteMax[i] = [
68 [ max(RouteMax[i-1]左 + a[i] , RouteMax[i-1]右 + a[i]) i >= 1
69
70
71 //暂时将储存结构看成一维数组,a[i]为当前层结点,RouteMax[i]为目前最大路径和
72
73
74
75
76 3、按自底向上的方式计算最优解的值
77 (计算出最大路径和并记录，其实我这里应该没有最到自底向上的方式，而是采用了自顶向下的备忘录
78 方式，记录每一个子问题的解.如果不用记录路径的话，应该就可以很自然而然地采用自底向上的方式，
79 从最后一个结点出发，而且不用记录路径，代码会减少很多。//后面会给出网络上别人的解法)
80
81 在计算最大路径和的时候，用表b来累加记录每一个结点，在求最大路径和的值。用表iPos来记录
82 每一层最大路径和经过的结点。其中每一个iPos[i],都由第i+1层决定，因为是不是最大，只有下
83 一层才能决定.
84
85 PS:表b定义了一种新结构，方便记录
86
87
88 4、由计算出的结果构造一个最优解(输出最大值和路径)
89
90 因为在第3步已经用表iPos记录了路径，所以直接遍历一次表iPos即可输出路径.
91
92
93 -----------------------------------------------------------------------
94
95 PS:刚刚看完《算法导论》动态规划这一章，所以想拿一道题来看看自己有没有理解到。
96
97 虽然算法思想已经有书本提供，但是实际想+写+调试也差不多用了一个上午+下午的时间
98
99 而且还不知道理解得对不对，还有做得对不对。所以如果有错误，希望前辈们指出。谢谢
100
101
102 5、算法分析：
103 算法的主要时间应该都是花费在LargestWay计算最大值以及记录路径上面，里面有一个双重迭代，外加一个for,一些常数时间的操作
104 时间复杂度应该是O(n^2)（失败。。。）
105 辅助空间比较多，主要是用在表b上面，是O（n^2）么？
106
107
--------------------------------------------------------------------------------------------- */
108
109
110#include<stdio.h>
111
112
113#define MAX 100
114
115typedef struct Array //定义一个种新结构方便记录
116
{
117 int iLeft ; //最大值是从左传给当前结点的
118 int iRight ; //最大值是从右传给当前结点的
119 int iSum ; //当前结点的值
120} Array ;
121
122
123
124int LargestWay(int a[][MAX], Array b[][MAX] ,int *p ,int n ) ;
125
126
127
128int main(void)
129{
130
131 int a[MAX][MAX] ;
132
133 Array b[MAX][MAX] ;
134
135 int iPos[MAX] ; //定位每一层中最大的元素
136
137 int i = 0 ;
138
139 int j = 0 ;
140
141 int t = 0 ;
142
143 int iSum = 0 ; //最大值
144
145 int k = 0 ;
146
147 while(scanf("%d",&t) || 0 == t)
148
{
149
150 for(i = 0 ; i < t ; i++)
151 {
152 for(j = 0 ; j <= i ; j++)
153 {
154 scanf("%d",&a[i][j]) ;
155
156 b[i][j].iSum = a[i][j] ;
157 b[i][j].iLeft = b[i][j].iRight = b[i][j].iSum ;
158
159
}
160 }
161
162
163 iSum = LargestWay(a,b,iPos,t) ;
164
165 for(i = 0 ; i < t ; i++) //表的作用在于此
166 {
167 printf("%d\n",a[i][iPos[i]]);
168 }
169
170 printf("%d\n\n",iSum) ;
171
172
173 }
174
175 return 0 ;
176}
177
178
179int LargestWay(int a[][MAX], Array b[][MAX] ,int *p ,int n )
180{
181 int i = 0 ;
182 int j = 0 ;
183 int iMax = a[0][0] ; // 0或者更佳
184
185 p[0] = 0 ; //第一个位置无庸置疑
186
187
188 //从第一个结点，开始将最大值往下传，Array的左右成员就是记录路径用的
189
190 for(i = 1 ; i < n ; i++)
191 {
192 for(j = 0 ,iMax = 0 ; j <= i ; j++)
193 {
194 if(0 == j ) //三角形左边界的结点
195 {
196 b[i][j].iLeft += b[i-1][j].iSum ;
197 b[i][j].iRight = 0 ;
198
199 b[i][j].iSum = ( b[i][j].iLeft > b[i][j].iRight ) ? b[i][j].iLeft : b[i][j].iRight ;
200
201 if(b[i][j].iSum >= iMax)
202 {
203 p[i-1] = j ; //修改一下数组定位，原来是p[i] = j
204 iMax = b[i][j].iSum ;
205 }
206
207 } // if
208
209
210 else if(i == j) //三角形右边界的结点
211 {
212 b[i][j].iRight += b[i-1][j-1].iSum ;
213 b[i][j].iLeft = 0 ;
214
215 b[i][j].iSum = ( b[i][j].iLeft > b[i][j].iRight ) ? b[i][j].iLeft : b[i][j].iRight ;
216
217 if(b[i][j].iSum >= iMax)
218 {
219 p[i-1] = j - 1 ;
220 iMax = b[i][j].iSum ;
221 }
222
223 }//else -if
224
225 else /**/////三角形中间的结点
226 {
227 b[i][j].iLeft += b[i-1][j].iSum ;
228 b[i][j].iRight += b[i-1][j-1].iSum ;
229
230 b[i][j].iSum = ( b[i][j].iLeft > b[i][j].iRight ) ? b[i][j].iLeft : b[i][j].iRight ;
231
232 if(b[i][j].iSum >= iMax)
233 {
234 p[i-1] = ( b[i][j].iLeft > b[i][j].iRight ) ? j : j - 1; //要么是j-1 要么是j
235 iMax = b[i][j].iSum ;
236 }
237
238 } //else -if
239
240 }//inside for
241 }//outside for
242
243// 蹩脚特殊处理
244 p[0] = 0 ;
245
246 for(i = 0 ; i < n ; i++)
247 {
248 if(iMax == b[n-1][i].iSum) //找出最大值通过的最后一个结点。
249 {
250 p[n-1] = i ;
251 }
252 }
253
254//末
255 return iMax ;
256}
257
258
259
260
261
262
263
264
265
266----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
267
268
269
270/**//* -----------------------------------
271
272 网络上别人的解法，不用记录路径，动态规划法
273
274 ------------------------------- */
275
276
277
278#include<iostream>
279
280using namespace std ;
281int main()
282{
283 int i,j,n;
284 int a[105][105];
285 cin>>n;
286 for(i=1;i<=n;i++)
287 for(j=1;j<i+1;j++)
288 cin>>a[i][j];
289
290
291 cout << "answer \n" ;
292
293 for(i=n-1;i>0;i--)
294 for(j=1;j<=i;j++)
295 {
296 if(a[i+1][j]>=a[i+1][j+1])
297 a[i][j]+=a[i+1][j];
298 else
299 a[i][j]+=a[i+1][j+1];
300 }
301
302 cout<<a[1][1];
303
304 return 0;
305}
306
307
308
309
310
311
312
313
314
315
316