面试金典--9.10

题目描述：给你一堆箱子，箱子宽wi,高hi,深di。箱子不能翻转，将箱子堆起来，下面的箱子必须宽、高、深均大于上面的箱子。实现一个方法，使得堆起来的箱子高度和最大

思路：

（1）简单思路就是递归，判断以每个箱子为底的时候得到的最大高度，优化就是可以排除比当前底要大的。

（2）上面思路有很多重复计算，我们可以把这些记录下来，就是动态规划了。

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 #include <cmath>
11 #include <string>
12 #include <stdexcept>
13 #include <stack>
14 #include <map>
15 using namespace std;
16 
17 struct BOX
18 {
19     int w;
20     int h;
21     int d;
22     bool operator<(const BOX &pb)const
23     {
24         if(w < pb.w && h < pb.h && d < pb.d)
25         {
26             return true;
27         }
28         else
29         {
30             return false;
31         }
32     }
33 };
34 
35 vector<BOX> boxes;
36 map<BOX,int> dp;
37 int fun(BOX bottom)
38 {
39     int i;
40     int max_height = 0;
41     for(i = 0 ; i < boxes.size() ; ++i)
42     {
43         if(boxes[i] < bottom)
44         {
45             if(dp.find(boxes[i]) == dp.end())
46             {
47                 int t = fun(boxes[i]);
48                 dp[boxes[i]] = t;
49             }
50             if(dp[boxes[i]] > max_height)
51             {
52                 max_height = dp[boxes[i]];
53             }
54         }
55     }
56     return max_height+bottom.h;
57 }
58 
59 int main()
60 {
61     BOX t1;
62     t1.d = 1;
63     t1.h = 1;
64     t1.w = 1;
65     BOX t2;
66     t2.d = 2;
67     t2.w = 2;
68     t2.h = 2;
69     BOX t3;
70     t3.d = 3;
71     t3.h = 3;
72     t3.w = 3;
73     BOX t4;
74     t4.d = 2;
75     t4.h = 4;
76     t4.w = 3;
77 
78     boxes.push_back(t1);
79     boxes.push_back(t2);
80     boxes.push_back(t3);
81     boxes.push_back(t4);
82 
83     int i;
84     int max_height = 0;
85     for(i = 0 ; i < boxes.size() ; ++i)
86     {
87         max_height = max(max_height,fun(boxes[i]));
88     }
89     cout<<max_height<<endl;
90     return 0;
91 }