9.10 給你一堆n個箱子，箱子寬w，高h，深d。箱子不能翻轉，將箱子堆起來時，下面箱子的寬度、高度和深度必須大于上面的箱子。實現一個方法，搭出最高的一堆箱子，箱堆的高度為每個箱子高度的總和。
解法：
要解決此題，我們需要找到不同子問題之間的關系。
假設我們又以下這些箱子：b1、b2,...,bn。能夠堆出的最高箱堆的高度等于max（底部為b1的最高箱堆，底部為b2的最高箱堆，...，底部為bn的最高箱堆）。也就是說，只要試著用每個箱子作為箱堆底部并搭出可能的最高高度，就能找出箱對的最高高度。
回溯的實現方法：
#include<iostream> #include<vector> using namespace std;struct box {int height;int wide;int depth;box(int h,int w,int d):height(h),wide(w),depth(d) {} };bool isValid(vector<box> &path,box b) {if(path.empty())return true;box top=path[path.size()-1];return b.depth<top.depth&&b.height<top.height&&b.wide<top.wide; }void helper(vector<box> &boxes,vector<box> &path,int &maxHeight) {int i;for(i=0;i<boxes.size(); i++){if(isValid(path,boxes[i])){path.push_back(boxes[i]);helper(boxes,path,maxHeight);path.pop_back();}}if(i==boxes.size()){int j,sum=0;for(j=0; j<path.size(); j++){sum+=path[j].height;}if(sum>maxHeight)maxHeight=sum;return;} } int maxBoxTower(vector<box> &boxes) {vector<box> path;int maxHeight=0;helper(boxes,path,maxHeight);return maxHeight; }int main() {vector<box> b= {box(2,2,2),box(1,2,1),box(3,2,1),box(3,3,3)};cout<<maxBoxTower(b)<<endl; }
?
