You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack
a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple
instances of the same type of box.
Source:http://people.csail.mit.edu/bdean/6.046/dp/. The link also has video for explanation of solution.
TheBox Stacking problem is a variation of LIS problem. We need to build a maximum height stack.
Following are the key points to note in the problem statement:
1) A box can be placed on top of another box only if both width and depth of the upper placed box are smaller than width and depth of the lower box respectively.
2) We can rotate boxes. For example, if there is a box with dimensions {1x2x3} where 1 is height, 2×3 is base, then there can be three possibilities, {1x2x3}, {2x1x3} and {3x1x2}.
3) We can use multiple instances of boxes. What it means is, we can have two different rotations of a box as part of our maximum height stack.
Following is thesolutionbased onDP solution of LIS problem.
1)Generate all 3 rotations of all boxes. The size of rotation array becomes 3 times the size of original array. For simplicity, we consider depth as always smaller than or equal to width.
2)Sort the above generated 3n boxes in decreasing order of base area.
3)After sorting the boxes, the problem is same as LIS with following optimal substructure property.
MSH(i) = Maximum possible Stack Height with box i at top of stack
MSH(i) = { Max ( MSH(j) ) + height(i) } where j < i and width(j) > width(i) and depth(j) > depth(i).
If there is no such j then MSH(i) = height(i)
4)To get overall maximum height, we return max(MSH(i)) where 0 < i < n
3维的就确定下两维(底面积),根据底面积排序,然后找高度的LDS
package DP;
import java.util.Arrays;
import java.util.Comparator;
public class BoxStacking {
public static void main(String[] args) {
Box[] A = new Box[4];
A[0] = new Box(4,6,7);
A[1] = new Box(1,2,3);
A[2] = new Box(4,5,6);
A[3] = new Box(10,12,32);
int n = A.length;
System.out.println(maxStackHeight(A, n));
}
// Time Complexity: O(n^2) Auxiliary Space: O(n)
public static int maxStackHeight(Box[] A, int n){
/* Create an array of all rotations of given boxes
For example, for a box {1, 2, 3}, we consider three
instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */
Box[] rot = new Box[3*n];
int index = 0;
for(int i=0; i<n; i++){
rot[index] = A[i]; // Copy the original box
index++;
rot[index] = new Box(); // First rotation of box
rot[index].h = A[i].w;
rot[index].d = Math.max(A[i].h, A[i].d);
rot[index].w = Math.min(A[i].h, A[i].d);
index++;
rot[index] = new Box(); // Second rotation of box
rot[index].h = A[i].d;
rot[index].d = Math.max(A[i].h, A[i].w);
rot[index].w = Math.min(A[i].h, A[i].w);
index++;
}
n = 3*n; // Now the number of boxes is 3n
/* Sort the array ‘rot[]‘ in decreasing order, using library
function for quick sort */
Arrays.sort(rot, new Comparator<Box>() {
@Override
public int compare(Box o1, Box o2) { // 按底面积递减排序
return (o2.d*o2.w) - (o1.d*o1.w);
}
});
/* Initialize msh values for all indexes
msh[i] –> Maximum possible Stack Height with box i on top */
int[] msh = new int[n];
for(int i=0; i<n; i++){
msh[i] = rot[i].h;
}
/* Compute optimized msh values in bottom up manner */
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(rot[i].w<rot[j].w && rot[i].d<rot[j].d){
msh[i] = Math.max(msh[i], msh[j]+rot[i].h);
}
}
}
/* Pick maximum of all msh values */
int max = 0;
for(int i=0; i<n; i++){
max = Math.max(max, msh[i]);
}
return max;
}
public static class Box{
int h, w, d; // h –> height, w –> width, d –> depth
// for simplicity of solution, always keep w <= d
public Box(){
}
public Box(int h_, int w_, int d_){
h = h_;
w = w_;
d = d_;
}
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/http://people.csail.mit.edu/bdean/6.046/dp/
分享到:
相关推荐
利用Stacking针对北京市pm2.5数据进行回归预测,直接运行
1012-Stacking Cylinders
将概念相似度的计算问题看做分类问题,提出一种基于Stacking方法的多策略本体映射框架;利用Stacking方法组合多种概念相似度算法,进而提出基于Widrow-Hoff理论的元数据分类算法LMSMC。该框架中,第0层分类器使用...
针对传统时序分析方法不适用于监测大量级形变的问题,采用Stacking InSAR方法对沛北矿区地表沉降进行监测。与传统的永久散射体技术相比,Stacking InSAR方法具有可监测大量级形变、提高信噪比的优点。
主要的三类集成学习方法为装袋,提升和堆叠。目前,大型的数据挖掘比赛(如Kaggle),排名靠前的基本上都是集成机器学习模型或深度神经网络。 将训练好的所有基模型对整个训练集进行预测,第$ j $个基模型对第i个...
IDL批量实现影像多单波段合成LayerStacking,并进行滤波SavitzkyGolayFilter,然后再拆分为单波段
利用InSAR Stacking技术监测雷州半岛沉降 ,杜亚男,冯光财,由于长利用InSAR Stacking技术监测雷州半岛沉降期过量开采地下水,雷州半岛出现了大范围的地面沉降,并伴有地裂缝、坍塌等地质灾害,�
html 7 stacking level, 编写html分块,stacing level
https://github.com/echohandsome制作两层stacking结构理解留出法回顾交叉验证法回顾Stacking集成学习方法介绍留出法回顾
一种适用于卷积神经网络的Stacking算法.pdf
本文来自于博客园,本文主要使用机器学习算法来将个体机器学习器的结果结合在一起,这个方法就是Stacking,希望对您的学习有所帮助。 Ensemblelearning中文名叫做集成学习,它并不是一个单独的机器学习算法,而是将...
高光谱图像分类研究中,集成学习能够显著地提高分类效果。但是传统的并行多分类系统对基础分类器有较高要求,即要求差异性及分类均衡。为了解决这一问题,采用Stacking Learning的堆栈式学习方式,首先使用
为此,提出一种基于极限梯度提升(XGBoost)与Stacking模型融合的短期母线负荷预测方法。基于XGBoost建立多个母线负荷预测元模型,组合构成Stacking模型融合的元模型层,连接一个XGBoost模型对元模型进行融合,整体...
利用ENVI进行图层融合代码
本文来自于csdn,本文是基于《kaggle比赛集成指南》来进行总结的概述什么是集成学习,以及目前较为常用的技术。集成方法是指由多个弱分类器模型组成的整体模型,我们需要研究的是:①弱分类器模型的形式②这些弱分类...
IDL批量实现影像多单波段合成LayerStacking,并进行滤波SavitzkyGolayFilter,然后再拆分为单波段
本文要解决的问题为预测问题,即给出seer提取的癌症病人数据,如A病人的患病时长,性别,年龄等信息以及他是否死亡,通过训练后,给出某个病人的信息后就可以判定他是否死亡,具有一定的现实意义。同理还有股票涨跌...
基于加权Stacking集成学习的Tor匿名流量识别方法.docx
Stacking集成学习在销售预测中的应用.docx
Cortex-M4F的Lazy Stacking特性在RTOS上下文切换中的作用