首页 > 代码库 > careercup-递归和动态规划 9.10
careercup-递归和动态规划 9.10
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;}
careercup-递归和动态规划 9.10
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。