已知三个int数组w,l,h,分别表示每个箱子宽、长和高,同时给定箱子的数目n。请设计算法,将箱子都堆起来(箱子不能反转),且上面箱子的宽度和长度必须小于下面的箱子。返回值为能够堆出的最高的高度。要求n小于等于500。
测试样例:
[1,1,1],[1,1,1],[1,1,1]
返回:1
# -*- coding:utf-8 -*-
class Box:
def getHeight(self, w, l, h, n):
if n <= 0:
return 0
box = [(w[i], l[i], h[i]) for i in range(n)]
box.sort(key = lambda b: (b[0], b[1]), reverse=True)
height = [0] * n
for i in range(n):
height[i] = box[i][2]
for j in range(i - 1, -1, -1):
if box[j][0] > box[i][0] and box[j][1] > box[i][1]:
height[i] = max(height[i], height[j] + box[i][2])
return max(height)
class Box {
int f[501] = {0};
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//动态规划,转换为最长上升子序列问题
/*
1. 排序,箱子是随便摆的,但是最高的情况一定是从长/宽下到上递减
2. 如果上面的箱子长宽都小于下面的箱子那么dp[i]=dp[i-1]+max(h[i])
否则 dp[i]=h[i]
*/
//冒泡排序
for(int i = w.size()-1 ; i > 0; i--)
for(int j = w.size()-1; j > w.size()- 1 - i ; j--)
if(w[j] >= w[j-1])
{
swap(w[j],w[j-1]);
swap(l[j],l[j-1]);
swap(h[j],h[j-1]);
}
f[0] = h[0];
int maxv = f[0];
for(int i = 1; i < n; i++)
{
int fjmax = 0;
for(int j = 0; j<i; j++)
if(w[i] < w[j] && l[i] < l[j])
fjmax = max(fjmax,f[j]);
f[i] = fjmax+h[i];
maxv = max(maxv,f[i]);
}
return maxv;
}
}; class Box: """ lis 用来存放以boxes[i]为底的箱子之和的最大值。 当boxes[j]的长宽<boxes[i]的长宽时(j<i),boxes[i]可以放到boxes[j]的下面。 将boxes[i]与之前的底逐一比较,求出最大值,即为lis[i]的值。 """ def getHeight(self, w, l, h, n): boxes = [(w[i], l[i], h[i]) for i in range(n)] boxes.sort() lis = [boxes[i][-1] for i in range(n)] for i in range(1, n): for j in range(i): if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1]: h = lis[j] + boxes[i][-1] if lis[i] < h: lis[i] = h return max(lis)
// 还是一楼的方法好,佩服佩服, 打卡。。。。。
struct BoxTest {
int w,l,h;
};
class Box {
static bool compare(BoxTest *A, BoxTest *B) {
return A->w > B->w;
}
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
vector<BoxTest *> array;
for (int i = 0 ; i != n; i++) {
BoxTest *tmp = new BoxTest();
tmp->w = w[i];
tmp->l = l[i];
tmp->h = h[i];
array.push_back(tmp);
}
sort(array.begin(),array.end(),compare);
vector<int> f(n+1,0);
f[0] = array[0]->h;
int result = f[0];
for (int i = 1 ; i != n ; ++i) {
f[i] = array[i]->h;
int tmax = 0;
for (int j = i - 1 ; j >=0 ; --j) {
if (array[i]->w < array[j]->w && array[i]->l < array[j]->l)
tmax = max(tmax,f[j]);
}
f[i] += tmax;
result = max(f[i],result);
}
return result;
}
}; import java.util.*;
public class Box {
private int[] w;
private int[] l;
private int[] h;
private int[] maxH;
public int getHeight(int[] w, int[] l, int[] h, int n) {
sort(w,l,h);
this.w=w;
this.l=l;
this.h=h;
maxH=new int[n];
for(int i=0;i<n;++i){
maxH[i]=h[i];
}
int maxHeight=0;
for(int i=n-1;i>=0;--i){
int temp= calculate(i);
if(temp>maxHeight){
maxHeight=temp;
}
}
return maxHeight;
}
//计算以index为最底的箱子的最大高度,并存放在maxH的index处
public int calculate(int index){
int temp=h[index];
for(int i=index+1;i<h.length;++i){
if(putAonB(i,index)){
if(temp<h[index]+maxH[i]){
temp=h[index]+maxH[i];
}
}
}
maxH[index]=temp;
return temp;
}
//将盘子按照长度从大到小排序,若是长度相同,那么将宽度从大到小排序
public void sort(int[] w,int[] l,int[] h){
for(int i=1;i<w.length;++i){
for(int j=0;j<w.length-i;++j){
if(w[j]<w[j+1]){
swap(w,l,h,j,j+1);
}else if(w[j]==w[j+1]&&l[j]<l[j+1]){
swap(w,l,h,j,j+1);
}
}
}
}
public void swap(int[] w,int[] l,int[] h,int f, int t){
int temp=w[f];
w[f]=w[t];
w[t]=temp;
temp=h[f];
h[f]=h[t];
h[t]=temp;
temp=l[f];
l[f]=l[t];
l[t]=temp;
}
} class Box {
struct box{
int width, length, height;
box(int w, int l, int h) :width(w), length(l), height(h){}
};
public:
int getHeight(vector<int> width, vector<int> length, vector<int> height, int n)
{
vector<box> boxes;
boxes.reserve(n);
for (int i = 0; i < n; ++i) boxes.emplace_back(width[i], length[i], height[i]);
sort(boxes.begin(), boxes.end(),
[](const box& b1, const box& b2)
{
return b1.width < b2.width || b1.width == b2.width && b1.length < b2.length;
});
vector<int> dp(n);
int maxHeight = 0;
for (int i = 0; i < n; ++i)
{
dp[i] = boxes[i].height;
for (int j = i - 1; j >= 0; --j)
{
if (boxes[j].width < boxes[i].width && boxes[j].length < boxes[i].length)
dp[i] = max(dp[i], dp[j] + boxes[i].height);
}
maxHeight = max(maxHeight, dp[i]);
}
return maxHeight;
}
};
class Box {
public:
static int comp(vector<int> l, vector<int> r){
return l[0]<r[0];
}
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
vector<int> res(n, 0);
vector<vector<int> > temp(n, vector<int>(3, 0));
for(int i=0; i<n; i++){
temp[i][0] = w[i];
temp[i][1] = l[i];
temp[i][2] = h[i];
}
sort(temp.begin(), temp.end(), comp);
res[0] = temp[0][2];
for(int i=1; i<n; i++){
int num = 0;
for(int j=i-1; j>=0; j--){
if(temp[i][0]>temp[j][0] && temp[i][1]>temp[j][1]){
num = max(num, res[j]);
}
}
res[i] = temp[i][2]+num;
}
int num = 0;
for(int i=0; i<n; i++){
num = max(res[i], num);
}
return num;
}
};
#Python版
#最长递增子序列问题
# -*- coding:utf-8 -*-
class Box:
def getHeight(self, w, l, h, n):
if n<0:
return 0
box = [(w[i],l[i],h[i]) for i in range(n)]
box.sort(key=lambda b:(b[0],b[1]))
height = [0]*n
for i in range(n):
height[i] = box[i][2]
for j in range(i):
if box[i][0] > box[j][0] and box[i][1] > box[j][1]:
height[i] = max(height[i],height[j]+box[i][2])
return max(height)
print Box().getHeight([2768,542,832,844,2920,587,72,1724,447,809,672,2393,1235,2775,273,1165,1809,111,1263,2751,1068,2507,453,65,2338,1103,1093,2327,1995,1125,2340,1133,2123,1692,2215,140,1822,2144,2240,2916,1860,2226,698,846,2177,295],[821,2593,1581,2891,2853,1662,2747,2856,2178,865,383,523,809,998,312,237,1871,2730,823,676,568,1839,2063,1651,2704,2113,1316,2892,1874,270,1112,869,1099,1876,371,2298,2070,1514,2916,165,1043,1355,2852,1319,1979,1961],[771,2963,1599,1910,2317,2884,872,2463,949,341,2718,1500,1071,539,2463,1355,104,2989,1240,240,981,0,2172,3011,621,681,1178,2518,2766,615,460,2399,2443,2894,799,1726,2454,2099,2279,2911,2018,426,2896,224,2663,351],46)
public int getHeight(int[] w, int[] l, int[] h, int n) {
dp = new int[n];
for (int i = 0; i < n; i++) {
int t = f(i, w, l, h, n);
sum = sum < t ? t : sum;
}
return sum;
}
int sum, dp[];
int f(int k, int[] w, int[] l, int[] h, int n) { //第k个箱子能装最多的高度
if (dp[k] != 0) {
return dp[k];
}
int max = h[k];
for (int i = 0; i < n; i++) {
if (w[i] < w[k] && l[i] < l[k]) {
int t = f(i, w, l, h, n);
if (t + h[k] > max) {
max = t + h[k];
}
}
}
return dp[k] = max;
}
private void swap(int[] w, int i, int j) {
int temp = w[i];
w[i] = w[j];
w[j] = temp;
}
private void sort(int[] w, int[] l, int[] h) {
for (int i = 0; i < w.length; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (w[j] < w[j + 1]) {
swap(w, j + 1, j);
swap(l, j + 1, j);
swap(h, j + 1, j);
} else
break;
}
}
}
public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
sort(w, l, h);
int[] dp = new int[n];
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i) {
int maxh = h[i];
for (int j = 0; j < i; ++j) {
if (l[j] > l[i]) {
int t = dp[j] + h[i];
if (t > maxh) {
maxh = t;
}
}
}
dp[i] = maxh;
if (result < maxh)
result = maxh;
}
return result;
}
class Box {
int f[501] = {0}; //存放n个箱子的最大上升高度
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
for(int i = w.size()-1 ; i > 0; i--){
for(int j = w.size()-1; j > w.size()- 1 - i ; j--){
if(w[j] >= w[j-1]/*&& l[j] >= l[j-1]*/){
swap(w[j],w[j-1]);
swap(l[j],l[j-1]);
swap(h[j],h[j-1]);
}
}
}
for(int i = 0; i < w.size(); i++){
cout<<w[i]<<" "<<l[i]<<" "<<h[i]<<endl;
}
f[0] = h[0];
int maxv = f[0];
for(int i = 1; i < n; i++){
f[i] = h[i];
int tmax = 0;
for(int j = i-1; j >= 0; j--){
if(w[i] < w[j] && l[i] < l[j]){
tmax = max(tmax,f[j]);
}
}
f[i] += (tmax);
maxv = max(maxv,f[i]);
}
return maxv;
}
};
//经典的有向无环图模型的DP问题
//选择某个起点使之有向无环图的最大路径长度
import java.util.*;
public class Box {
public int getHeight(int[] w, int[] l, int[] h, int n) {
boolean[][] graph = new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(w[i]>w[j]&&l[i]>l[j])//使底部的箱子长宽大于上面的,若有箱子长宽小,则有到其的有向边
graph[i][j] = true;
}
}
int[] dp = new int[n];
int ans = 0;
for(int i=0;i<n;i++){//选择起点
int tmp = dfs(i,graph,h,dp);
ans = Math.max(ans,tmp);
}
return ans;
}
public int dfs(int bottom,boolean[][] graph,int[] h,int[] dp){
if(dp[bottom]>0) return dp[bottom];
int n = graph.length;
int top = 0;
for(int i=0;i<n;i++){
if(graph[bottom][i])
top=Math.max(top,dfs(i,graph,h,dp));
}
return dp[bottom] = top+h[bottom];//缓存当前结点的最大路径长度
}
} public int getHeight(int[] w, int[] l, int[] h, int n) {
// write code here
/*
* 按照宽度从大到小排序,定maxH[i]为从0开始到放入第i-1个箱子(第i-1个一定被放入),满足长宽条件的最大高度
* 从第1个开始为h[0],初始maxH[i] = h[i],tmax记录放入第i-1个箱子时可达到的最大高度
* 伪码如下:
* maxH[0] = h[0];
* res = maxH[0];
* for i = 1:n
* maxH[i] = h[i];
* tmax = 0;
* for j = i-1 : 0
* if l[j] > l[i] && w[j] > w[i]//看能放下当前i箱子的情况下,选择高度最大的那种
* tmax = max(tmax, maxH[j]);
* maxH[i] += tmax;
* res = max(res, maxH[i]);//res仅存到放入第i-1个箱子为止,出现过的高度最大值
* end for;
* return res;
*/
if(n <= 0){
return 0;
}
//sort
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(w[i] < w[j]){
swap(w, i, j);
swap(l, i, j);
swap(h, i, j);
}
}
}
//get height
int[] maxH = new int[n];
maxH[0] = h[0];
int res = maxH[0];
for(int i = 1; i < n; i++){
maxH[i] = h[i];
int tmax = 0;
for(int j = i-1; j >=0; j--){
if(w[j] > w[i] && l[j] > l[i]){
tmax = (tmax > maxH[j])? tmax : maxH[j];
}
}
maxH[i] += tmax;
res = res > maxH[i] ? res : maxH[i];
}
return res;
}
private void swap(int[] mat, int x, int y) {
// TODO Auto-generated method stub
int tmp = mat[x];
mat[x] = mat[y];
mat[y] = tmp;
}
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
for(int i=n-1;i>0;i--)
for(int j=n-1;j>n-i-1;j--)
if(w[j-1]<w[j]){
swap(w[j-1],w[j]);
swap(l[j-1],l[j]);
swap(h[j-1],h[j]); } int dp[503]; memset(dp,0,sizeof(dp)); dp[0] = h[0]; int Max= dp[0],t; for(int i=1;i<n;i++){ dp[i] = h[i]; t = 0; for(int j=i-1;j>=0;j--) if(w[i]<w[j] && l[i]<l[j]) t = max(t,dp[j]); dp[i] += t; Max = max(Max,dp[i]); } return Max;
}
};
# -*- coding:utf-8 -*- class Box: def getHeight(self, w, l, h, n): boxes = [] for i in range(n): boxes.append([w[i], l[i], h[i]]) boxes.sort(key=lambda x: x[0]) # print(boxes) dp = [0] * len(boxes) for i in range(n): dp[i] = boxes[i][2] for j in range(i): if boxes[j][1] < boxes[i][1] and boxes[j][0] < boxes[i][0]: dp[i] = max(dp[i], dp[j] + boxes[i][2]) # print(dp) return max(dp)
运行时间:179ms
占用内存:5728k
//严格的最大递增子序列问题
//先按照宽度排序(或者长度排序),然后从第一个点开始找起,看看本身能达到的最大高度;
//参考代码如下;
class Box {
public:
//交换数值;
void swap(int& a,int& b)
{
int temp=a;
a=b;
b=temp;
}
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//step1:按照宽度排列(冒泡排序法);
for(int i=0;i<w.size()-1;i++)
{
for(int j=i+1;j<w.size();j++)
{
if(w[j]>w[i])
{
swap(w[i],w[j]);
swap(l[i],l[j]);
swap(h[i],h[j]);
}
}
}
int maxH[200] = {0}; //存放n个箱子的最大上升高度;
maxH[0]=h[0];//第一个箱子得到的最大高度就是本身;
int res=maxH[0];
for(int i=1;i<n;i++)
{
maxH[i]=h[i];//该箱子的最小高度(至少)就是本身的高度;
int temp=0;
//下面这个for循环主要计算该点(前面)能够得到的最大高度;
for(int j=i-1;j>=0;j--)
{
if(w[j]>w[i] && l[j]>l[i])
{
temp=(temp>maxH[j])?temp:maxH[j];
}
}
//将本身的高度加上之前箱子可以得到的最大高度,得到现在的高度;
maxH[i]+=temp;
//该res主要不断维护最大值,不然还要在maxH数组中寻找最大值;
res=(res>maxH[i])?res:maxH[i];
}
return res;
}
};
class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
// 整体思路是,首先对n个箱子按照宽度或长度降序排列,这样可以保证高度最大的序列一定是这个序列的子序列(想一想为什么)。
// dp[i]表示的是在0~i号箱子组成的序列中,以i号箱子为顶的最大高度。
// 外层循环遍历0~n-1号箱子,求以每个箱子为顶的最大高度dp[i],最大的dp[i]即为答案。
// 内层循环对每个i,遍历前面0~i-1,找到i号箱子能够堆在其上的最高高度prev_max,那么dp[i]就等于i号箱子的高度加上prev_max。
// 选择排序
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (w[i] < w[j]) {
swap(w[i], w[j]);
swap(l[i], l[j]);
swap(h[i], h[j]);
}
}
}
// dp[i]表示的是在0~i号箱子组成的序列中,以i号箱子为顶的最大高度。
vector<int> dp(n);
dp[0] = h[0];
int maxh = dp[0];
for (int i = 1; i < n; ++i) {
dp[i] = h[i]; // dp[i]至少是i号箱子的高度
int prev_max = 0;
for (int j = i - 1; j >= 0; --j) {
if (w[i] < w[j] && l[i] < l[j]) { // 判断i号箱子能否堆在其上
prev_max = max(prev_max, dp[j]);
}
}
dp[i] += prev_max;
maxh = max(maxh, dp[i]);
}
return maxh;
}
}; class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// sort the box by weight
sortBox(w, l, h, n);
memset(dp, 0, sizeof(dp) );
dp[0] = h[0];
int maxHeight = dp[0];
for (int i = 1; i < n; ++i) {
dp[i] = h[i];
for (int j = 0; j < i; ++j) {
if(w[i] < w[j] && l[i] < l[j]) {
if (dp[j] + h[i] > dp[i]) {
dp[i] = dp[j] + h[i];
}
}
}
if (dp[i] > maxHeight) {
maxHeight = dp[i];
}
}
return maxHeight;
}
private:
void swapBox(int &a, int &b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
void sortBox(vector<int> &w, vector<int> &l, vector<int> &h, int n) {
for (int i = 0; i < n; ++i) {
bool flag = false;
for (int j = 0; j < n-i-1; ++j) {
if (w[j] <= w[j+1]) {
swapBox(w[j], w[j+1]);
swapBox(l[j], l[j+1]);
swapBox(h[j], h[j+1]);
flag = true;
}
}
if (!flag) {
break;
}
}
}
int dp[503] = {0};
}; class Box {
public:
int getHeight(vector<int> w, vector<int> l, vector<int> h, int n) {
// write code here
//按照宽度降序,冒泡排序
for(int i=0;i<n;++i)
for(int j=0;j<n-i-1;j++)
{
if(w[j]<w[j+1])
{
swap(w[j+1],w[j]);
swap(l[j+1],l[j]);
swap(h[j+1],h[j]);
}
}
vector<int>dp(n,0);
int max_height=0;
for(int i=0;i<n;++i)
{
dp[i]=h[i];
int height=h[i];
for(int j=0;j<i;++j)
{
if(w[j]>w[i]&&l[j]>l[i])
dp[i]=max(dp[j]+height,dp[i]);
}
max_height=max(max_height,dp[i]);
}
return max_height;
}
};
//这道题应用了求最大上升子序列的问题,和最大上升子序列不同的是,最大子序列的序列元素的相对位置是固定的,而堆箱子问题的序列元素的
//相对位置是可变的,要想求出堆箱子的最大高度,就要尽量使宽度和长度按照降序排列,因为两者不能同时排列,所以只能先按照一个排列,
//然后选择另一个满足条件的,上面的代码中使用了冒泡排序的方法
//dp数组中,dp[i]表示的是以第i个箱子为顶点(第i个箱子必须被选到)的可堆积的最大高度