Tower of the boxes












-3















We have N boxes. Each box has 3 params: width, length, height.



I need to write a function that generates the highest possible tower using this boxes.
Function must obey the following rule: all params of bottom box should be bigger than box above it.



Example



Let's say we have a box described as int array {width, length, height} -> {1, 2, 5}, then:



input: boxes = {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



output: 8 since {4, 5, 4} greater than {2, 2, 3} greater than {1, 1, 1}



Solution



I have found one solution that I can not understand.



void sortArrDesc(int array) {
Arrays.sort(array, new java.util.Comparator<int>() {
public int compare(int a, int b) {
return -1 * Integer.compare(a[2], b[2]);
}
});
}

boolean canPlaceOnTop(int prevBoxIndex, int currBoxIndex, int boxes) {
if (prevBoxIndex == -1) return true;
int bottomBox = boxes[prevBoxIndex];
int topBox = boxes[currBoxIndex];

return (bottomBox[0] > topBox[0] &&
bottomBox[1] > topBox[1] &&
bottomBox[2] > topBox[2]);
}

int getHighestTower(int prevBoxIndex, int currBoxIndex, int boxes) {
if (currBoxIndex == boxes.length) return 0;

int nextBoxIndex = currBoxIndex + 1;

int heightWithCurrBox = 0;

if (canPlaceOnTop(prevBoxIndex, currBoxIndex, boxes)) {
int currentBoxHeight = boxes[currBoxIndex][2];
int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes);
heightWithCurrBox = heightNextBox + currentBoxHeight;
}

int heightWithoutCurrBox =
getHighestTower(prevBoxIndex, nextBoxIndex, boxes);


return Math.max(heightWithCurrBox, heightWithoutCurrBox);
}

int getHighestTower(int boxes) {
sortArrDesc(boxes);
return getHighestTower(-1, 0, boxes);
}


I don't understand what exactly getHighestTower function do.



I mean when for example, I call function Math.sqrt(5) I understand that I will get square root of 5. But here, in getHighestTower function something strange happening.



It is clear that call getHighestTower(-1, 0, boxes) will return the highest tower.



But! When we do recursive calls, I do not understand what they means.
getHighestTower(prevBoxIndex, nextBoxIndex, boxes)



What does this line means?



It seems like that call should return max possible height starting from nextBox, but then why do we need to use prevBoxIndex?



Moreover, this call getHighestTower(currBoxIndex, nextBoxIndex, boxes); looks like do the same, but instead of prevBoxIndex we use currBoxIndex why is that?



P.S. I have already found this question, but it doesn't contain any useful information.










share|improve this question

























  • prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

    – user3386109
    Nov 26 '18 at 21:42













  • Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

    – SomeDude
    Nov 26 '18 at 21:43











  • @user3386109 could you explain in more details why we need prevBoxIndex?

    – No Name QA
    Nov 26 '18 at 22:35











  • For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

    – user3386109
    Nov 26 '18 at 22:57













  • @user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

    – No Name QA
    Nov 27 '18 at 8:04


















-3















We have N boxes. Each box has 3 params: width, length, height.



I need to write a function that generates the highest possible tower using this boxes.
Function must obey the following rule: all params of bottom box should be bigger than box above it.



Example



Let's say we have a box described as int array {width, length, height} -> {1, 2, 5}, then:



input: boxes = {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



output: 8 since {4, 5, 4} greater than {2, 2, 3} greater than {1, 1, 1}



Solution



I have found one solution that I can not understand.



void sortArrDesc(int array) {
Arrays.sort(array, new java.util.Comparator<int>() {
public int compare(int a, int b) {
return -1 * Integer.compare(a[2], b[2]);
}
});
}

boolean canPlaceOnTop(int prevBoxIndex, int currBoxIndex, int boxes) {
if (prevBoxIndex == -1) return true;
int bottomBox = boxes[prevBoxIndex];
int topBox = boxes[currBoxIndex];

return (bottomBox[0] > topBox[0] &&
bottomBox[1] > topBox[1] &&
bottomBox[2] > topBox[2]);
}

int getHighestTower(int prevBoxIndex, int currBoxIndex, int boxes) {
if (currBoxIndex == boxes.length) return 0;

int nextBoxIndex = currBoxIndex + 1;

int heightWithCurrBox = 0;

if (canPlaceOnTop(prevBoxIndex, currBoxIndex, boxes)) {
int currentBoxHeight = boxes[currBoxIndex][2];
int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes);
heightWithCurrBox = heightNextBox + currentBoxHeight;
}

int heightWithoutCurrBox =
getHighestTower(prevBoxIndex, nextBoxIndex, boxes);


return Math.max(heightWithCurrBox, heightWithoutCurrBox);
}

int getHighestTower(int boxes) {
sortArrDesc(boxes);
return getHighestTower(-1, 0, boxes);
}


I don't understand what exactly getHighestTower function do.



I mean when for example, I call function Math.sqrt(5) I understand that I will get square root of 5. But here, in getHighestTower function something strange happening.



It is clear that call getHighestTower(-1, 0, boxes) will return the highest tower.



But! When we do recursive calls, I do not understand what they means.
getHighestTower(prevBoxIndex, nextBoxIndex, boxes)



What does this line means?



It seems like that call should return max possible height starting from nextBox, but then why do we need to use prevBoxIndex?



Moreover, this call getHighestTower(currBoxIndex, nextBoxIndex, boxes); looks like do the same, but instead of prevBoxIndex we use currBoxIndex why is that?



P.S. I have already found this question, but it doesn't contain any useful information.










share|improve this question

























  • prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

    – user3386109
    Nov 26 '18 at 21:42













  • Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

    – SomeDude
    Nov 26 '18 at 21:43











  • @user3386109 could you explain in more details why we need prevBoxIndex?

    – No Name QA
    Nov 26 '18 at 22:35











  • For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

    – user3386109
    Nov 26 '18 at 22:57













  • @user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

    – No Name QA
    Nov 27 '18 at 8:04
















-3












-3








-3








We have N boxes. Each box has 3 params: width, length, height.



I need to write a function that generates the highest possible tower using this boxes.
Function must obey the following rule: all params of bottom box should be bigger than box above it.



Example



Let's say we have a box described as int array {width, length, height} -> {1, 2, 5}, then:



input: boxes = {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



output: 8 since {4, 5, 4} greater than {2, 2, 3} greater than {1, 1, 1}



Solution



I have found one solution that I can not understand.



void sortArrDesc(int array) {
Arrays.sort(array, new java.util.Comparator<int>() {
public int compare(int a, int b) {
return -1 * Integer.compare(a[2], b[2]);
}
});
}

boolean canPlaceOnTop(int prevBoxIndex, int currBoxIndex, int boxes) {
if (prevBoxIndex == -1) return true;
int bottomBox = boxes[prevBoxIndex];
int topBox = boxes[currBoxIndex];

return (bottomBox[0] > topBox[0] &&
bottomBox[1] > topBox[1] &&
bottomBox[2] > topBox[2]);
}

int getHighestTower(int prevBoxIndex, int currBoxIndex, int boxes) {
if (currBoxIndex == boxes.length) return 0;

int nextBoxIndex = currBoxIndex + 1;

int heightWithCurrBox = 0;

if (canPlaceOnTop(prevBoxIndex, currBoxIndex, boxes)) {
int currentBoxHeight = boxes[currBoxIndex][2];
int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes);
heightWithCurrBox = heightNextBox + currentBoxHeight;
}

int heightWithoutCurrBox =
getHighestTower(prevBoxIndex, nextBoxIndex, boxes);


return Math.max(heightWithCurrBox, heightWithoutCurrBox);
}

int getHighestTower(int boxes) {
sortArrDesc(boxes);
return getHighestTower(-1, 0, boxes);
}


I don't understand what exactly getHighestTower function do.



I mean when for example, I call function Math.sqrt(5) I understand that I will get square root of 5. But here, in getHighestTower function something strange happening.



It is clear that call getHighestTower(-1, 0, boxes) will return the highest tower.



But! When we do recursive calls, I do not understand what they means.
getHighestTower(prevBoxIndex, nextBoxIndex, boxes)



What does this line means?



It seems like that call should return max possible height starting from nextBox, but then why do we need to use prevBoxIndex?



Moreover, this call getHighestTower(currBoxIndex, nextBoxIndex, boxes); looks like do the same, but instead of prevBoxIndex we use currBoxIndex why is that?



P.S. I have already found this question, but it doesn't contain any useful information.










share|improve this question
















We have N boxes. Each box has 3 params: width, length, height.



I need to write a function that generates the highest possible tower using this boxes.
Function must obey the following rule: all params of bottom box should be bigger than box above it.



Example



Let's say we have a box described as int array {width, length, height} -> {1, 2, 5}, then:



input: boxes = {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



output: 8 since {4, 5, 4} greater than {2, 2, 3} greater than {1, 1, 1}



Solution



I have found one solution that I can not understand.



void sortArrDesc(int array) {
Arrays.sort(array, new java.util.Comparator<int>() {
public int compare(int a, int b) {
return -1 * Integer.compare(a[2], b[2]);
}
});
}

boolean canPlaceOnTop(int prevBoxIndex, int currBoxIndex, int boxes) {
if (prevBoxIndex == -1) return true;
int bottomBox = boxes[prevBoxIndex];
int topBox = boxes[currBoxIndex];

return (bottomBox[0] > topBox[0] &&
bottomBox[1] > topBox[1] &&
bottomBox[2] > topBox[2]);
}

int getHighestTower(int prevBoxIndex, int currBoxIndex, int boxes) {
if (currBoxIndex == boxes.length) return 0;

int nextBoxIndex = currBoxIndex + 1;

int heightWithCurrBox = 0;

if (canPlaceOnTop(prevBoxIndex, currBoxIndex, boxes)) {
int currentBoxHeight = boxes[currBoxIndex][2];
int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes);
heightWithCurrBox = heightNextBox + currentBoxHeight;
}

int heightWithoutCurrBox =
getHighestTower(prevBoxIndex, nextBoxIndex, boxes);


return Math.max(heightWithCurrBox, heightWithoutCurrBox);
}

int getHighestTower(int boxes) {
sortArrDesc(boxes);
return getHighestTower(-1, 0, boxes);
}


I don't understand what exactly getHighestTower function do.



I mean when for example, I call function Math.sqrt(5) I understand that I will get square root of 5. But here, in getHighestTower function something strange happening.



It is clear that call getHighestTower(-1, 0, boxes) will return the highest tower.



But! When we do recursive calls, I do not understand what they means.
getHighestTower(prevBoxIndex, nextBoxIndex, boxes)



What does this line means?



It seems like that call should return max possible height starting from nextBox, but then why do we need to use prevBoxIndex?



Moreover, this call getHighestTower(currBoxIndex, nextBoxIndex, boxes); looks like do the same, but instead of prevBoxIndex we use currBoxIndex why is that?



P.S. I have already found this question, but it doesn't contain any useful information.







java algorithm recursion






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 26 '18 at 21:11







No Name QA

















asked Nov 26 '18 at 20:08









No Name QANo Name QA

142111




142111













  • prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

    – user3386109
    Nov 26 '18 at 21:42













  • Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

    – SomeDude
    Nov 26 '18 at 21:43











  • @user3386109 could you explain in more details why we need prevBoxIndex?

    – No Name QA
    Nov 26 '18 at 22:35











  • For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

    – user3386109
    Nov 26 '18 at 22:57













  • @user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

    – No Name QA
    Nov 27 '18 at 8:04





















  • prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

    – user3386109
    Nov 26 '18 at 21:42













  • Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

    – SomeDude
    Nov 26 '18 at 21:43











  • @user3386109 could you explain in more details why we need prevBoxIndex?

    – No Name QA
    Nov 26 '18 at 22:35











  • For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

    – user3386109
    Nov 26 '18 at 22:57













  • @user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

    – No Name QA
    Nov 27 '18 at 8:04



















prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

– user3386109
Nov 26 '18 at 21:42







prevBoxIndex is the index of the box on top of the stack (that box is needed by the canPlaceOnTop method). currBoxIndex is the index of a box which may or may not be added to the stack. This is basically a depth-first search.

– user3386109
Nov 26 '18 at 21:42















Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

– SomeDude
Nov 26 '18 at 21:43





Why is not the output 11 ? I see the following output is valid : {4,5,4} -> {3,3,3} -> {2,2,3} -> {1,1,1} ? Is it a requirement that all dimensions should be strictly larger to define "bigger" ?

– SomeDude
Nov 26 '18 at 21:43













@user3386109 could you explain in more details why we need prevBoxIndex?

– No Name QA
Nov 26 '18 at 22:35





@user3386109 could you explain in more details why we need prevBoxIndex?

– No Name QA
Nov 26 '18 at 22:35













For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

– user3386109
Nov 26 '18 at 22:57







For example, prevBoxIndex is 100, and currBoxIndex is 101. Then the function will check if box 101 can be placed on box 100. If it can, the first recursive call is getHighestTower(101,102,boxes). The second recursive call is getHighestTower(100,102,boxes). In other words, the first call uses box 101. The second call skips box 101, and finds the best height starting with an attempt to put box 102 on top of box 100.

– user3386109
Nov 26 '18 at 22:57















@user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

– No Name QA
Nov 27 '18 at 8:04







@user3386109 Thank you!. According to your comment recursive calls work in the following manner: The getHighestTower(101,102,boxes) call calculates the highest possible tower using h1 = boxes[101] + boxes[102] + ... + the lowest box. And the getHighestTower(101,102,boxes) call calculates the highest possible tower using h2 = boxes[100] + boxes[102] + ... + the lowest box. If it's true, then why we add height of box[101] to result of the getHighestTower(101,102,boxes) if it already calculated by recursion?

– No Name QA
Nov 27 '18 at 8:04














1 Answer
1






active

oldest

votes


















0














This problem could be solved like this:




  1. Sort the boxes by height.


  2. Then the problem is to look for the increasing subsequence whose sum of heights is maximum - here "increasing" would mean :



currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight



For the input {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



lets say the sorted by height array is :



{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}



then the increasing subsequence with the above criterion is



{1,1,1}, {3,3,3}, {4,5,4}



Then height is 1 + 3 + 4 = 8.



Why do you need to sort by height first ?
Because, lets say the input is



{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}



and is not sorted by height, then the increasing subsequence by above criterion would yield



{1,1,1}, {3,3,3}



and it gives answer as 1 + 3 = 4 which is not optimal.



Code in Java:



 private static int getHeighestTower( int x ) {
Arrays.sort( x, new Comparator<int>() {
@Override
public int compare( int a, int b ) {
return a[2] - b[2];
}
});

int L = new int[x.length];
Arrays.fill(L,1);
int max = 0;
int h = 0;
int hi = 0;
for ( int i = 0; i < x.length; i++ ) {
hi = x[i][2];
int lastAdded = 0;
for ( int j = 0; j < i; j++ ) {
if ( aBiggerThanB(x[i], x[j]) ) {
if ( L[i] < 1 + L[j] ) {
L[i] = 1 + L[j];
hi += x[j][2];
lastAdded = x[j][2];
} else if ( L[i] == 1 + L[j] ) {
hi = Math.max( hi, hi - lastAdded + x[j][2]);
}
}
}
h = Math.max( h, hi);
max = Math.max( max, L[i] );
}

return h;
}

private static boolean aBiggerThanB( int a, int b ) {
return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}





share|improve this answer


























  • I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

    – No Name QA
    Nov 26 '18 at 22:34











  • @NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

    – SomeDude
    Nov 26 '18 at 22:37











  • The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

    – No Name QA
    Nov 26 '18 at 22:39













  • Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

    – No Name QA
    Nov 27 '18 at 9:39











  • @NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

    – SomeDude
    Nov 27 '18 at 15:22











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53488279%2ftower-of-the-boxes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









0














This problem could be solved like this:




  1. Sort the boxes by height.


  2. Then the problem is to look for the increasing subsequence whose sum of heights is maximum - here "increasing" would mean :



currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight



For the input {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



lets say the sorted by height array is :



{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}



then the increasing subsequence with the above criterion is



{1,1,1}, {3,3,3}, {4,5,4}



Then height is 1 + 3 + 4 = 8.



Why do you need to sort by height first ?
Because, lets say the input is



{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}



and is not sorted by height, then the increasing subsequence by above criterion would yield



{1,1,1}, {3,3,3}



and it gives answer as 1 + 3 = 4 which is not optimal.



Code in Java:



 private static int getHeighestTower( int x ) {
Arrays.sort( x, new Comparator<int>() {
@Override
public int compare( int a, int b ) {
return a[2] - b[2];
}
});

int L = new int[x.length];
Arrays.fill(L,1);
int max = 0;
int h = 0;
int hi = 0;
for ( int i = 0; i < x.length; i++ ) {
hi = x[i][2];
int lastAdded = 0;
for ( int j = 0; j < i; j++ ) {
if ( aBiggerThanB(x[i], x[j]) ) {
if ( L[i] < 1 + L[j] ) {
L[i] = 1 + L[j];
hi += x[j][2];
lastAdded = x[j][2];
} else if ( L[i] == 1 + L[j] ) {
hi = Math.max( hi, hi - lastAdded + x[j][2]);
}
}
}
h = Math.max( h, hi);
max = Math.max( max, L[i] );
}

return h;
}

private static boolean aBiggerThanB( int a, int b ) {
return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}





share|improve this answer


























  • I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

    – No Name QA
    Nov 26 '18 at 22:34











  • @NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

    – SomeDude
    Nov 26 '18 at 22:37











  • The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

    – No Name QA
    Nov 26 '18 at 22:39













  • Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

    – No Name QA
    Nov 27 '18 at 9:39











  • @NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

    – SomeDude
    Nov 27 '18 at 15:22
















0














This problem could be solved like this:




  1. Sort the boxes by height.


  2. Then the problem is to look for the increasing subsequence whose sum of heights is maximum - here "increasing" would mean :



currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight



For the input {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



lets say the sorted by height array is :



{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}



then the increasing subsequence with the above criterion is



{1,1,1}, {3,3,3}, {4,5,4}



Then height is 1 + 3 + 4 = 8.



Why do you need to sort by height first ?
Because, lets say the input is



{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}



and is not sorted by height, then the increasing subsequence by above criterion would yield



{1,1,1}, {3,3,3}



and it gives answer as 1 + 3 = 4 which is not optimal.



Code in Java:



 private static int getHeighestTower( int x ) {
Arrays.sort( x, new Comparator<int>() {
@Override
public int compare( int a, int b ) {
return a[2] - b[2];
}
});

int L = new int[x.length];
Arrays.fill(L,1);
int max = 0;
int h = 0;
int hi = 0;
for ( int i = 0; i < x.length; i++ ) {
hi = x[i][2];
int lastAdded = 0;
for ( int j = 0; j < i; j++ ) {
if ( aBiggerThanB(x[i], x[j]) ) {
if ( L[i] < 1 + L[j] ) {
L[i] = 1 + L[j];
hi += x[j][2];
lastAdded = x[j][2];
} else if ( L[i] == 1 + L[j] ) {
hi = Math.max( hi, hi - lastAdded + x[j][2]);
}
}
}
h = Math.max( h, hi);
max = Math.max( max, L[i] );
}

return h;
}

private static boolean aBiggerThanB( int a, int b ) {
return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}





share|improve this answer


























  • I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

    – No Name QA
    Nov 26 '18 at 22:34











  • @NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

    – SomeDude
    Nov 26 '18 at 22:37











  • The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

    – No Name QA
    Nov 26 '18 at 22:39













  • Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

    – No Name QA
    Nov 27 '18 at 9:39











  • @NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

    – SomeDude
    Nov 27 '18 at 15:22














0












0








0







This problem could be solved like this:




  1. Sort the boxes by height.


  2. Then the problem is to look for the increasing subsequence whose sum of heights is maximum - here "increasing" would mean :



currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight



For the input {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



lets say the sorted by height array is :



{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}



then the increasing subsequence with the above criterion is



{1,1,1}, {3,3,3}, {4,5,4}



Then height is 1 + 3 + 4 = 8.



Why do you need to sort by height first ?
Because, lets say the input is



{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}



and is not sorted by height, then the increasing subsequence by above criterion would yield



{1,1,1}, {3,3,3}



and it gives answer as 1 + 3 = 4 which is not optimal.



Code in Java:



 private static int getHeighestTower( int x ) {
Arrays.sort( x, new Comparator<int>() {
@Override
public int compare( int a, int b ) {
return a[2] - b[2];
}
});

int L = new int[x.length];
Arrays.fill(L,1);
int max = 0;
int h = 0;
int hi = 0;
for ( int i = 0; i < x.length; i++ ) {
hi = x[i][2];
int lastAdded = 0;
for ( int j = 0; j < i; j++ ) {
if ( aBiggerThanB(x[i], x[j]) ) {
if ( L[i] < 1 + L[j] ) {
L[i] = 1 + L[j];
hi += x[j][2];
lastAdded = x[j][2];
} else if ( L[i] == 1 + L[j] ) {
hi = Math.max( hi, hi - lastAdded + x[j][2]);
}
}
}
h = Math.max( h, hi);
max = Math.max( max, L[i] );
}

return h;
}

private static boolean aBiggerThanB( int a, int b ) {
return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}





share|improve this answer















This problem could be solved like this:




  1. Sort the boxes by height.


  2. Then the problem is to look for the increasing subsequence whose sum of heights is maximum - here "increasing" would mean :



currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight



For the input {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}



lets say the sorted by height array is :



{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}



then the increasing subsequence with the above criterion is



{1,1,1}, {3,3,3}, {4,5,4}



Then height is 1 + 3 + 4 = 8.



Why do you need to sort by height first ?
Because, lets say the input is



{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}



and is not sorted by height, then the increasing subsequence by above criterion would yield



{1,1,1}, {3,3,3}



and it gives answer as 1 + 3 = 4 which is not optimal.



Code in Java:



 private static int getHeighestTower( int x ) {
Arrays.sort( x, new Comparator<int>() {
@Override
public int compare( int a, int b ) {
return a[2] - b[2];
}
});

int L = new int[x.length];
Arrays.fill(L,1);
int max = 0;
int h = 0;
int hi = 0;
for ( int i = 0; i < x.length; i++ ) {
hi = x[i][2];
int lastAdded = 0;
for ( int j = 0; j < i; j++ ) {
if ( aBiggerThanB(x[i], x[j]) ) {
if ( L[i] < 1 + L[j] ) {
L[i] = 1 + L[j];
hi += x[j][2];
lastAdded = x[j][2];
} else if ( L[i] == 1 + L[j] ) {
hi = Math.max( hi, hi - lastAdded + x[j][2]);
}
}
}
h = Math.max( h, hi);
max = Math.max( max, L[i] );
}

return h;
}

private static boolean aBiggerThanB( int a, int b ) {
return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
}






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 27 '18 at 15:50

























answered Nov 26 '18 at 22:22









SomeDudeSomeDude

4,37531327




4,37531327













  • I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

    – No Name QA
    Nov 26 '18 at 22:34











  • @NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

    – SomeDude
    Nov 26 '18 at 22:37











  • The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

    – No Name QA
    Nov 26 '18 at 22:39













  • Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

    – No Name QA
    Nov 27 '18 at 9:39











  • @NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

    – SomeDude
    Nov 27 '18 at 15:22



















  • I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

    – No Name QA
    Nov 26 '18 at 22:34











  • @NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

    – SomeDude
    Nov 26 '18 at 22:37











  • The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

    – No Name QA
    Nov 26 '18 at 22:39













  • Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

    – No Name QA
    Nov 27 '18 at 9:39











  • @NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

    – SomeDude
    Nov 27 '18 at 15:22

















I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

– No Name QA
Nov 26 '18 at 22:34





I'm sorry but how is your answer connected with my question? I understand why we sort boxes. I do not understand what recursion does, because of two params prevBoxIndex and currBoxIndex. I can not understand the idea behind what recursion calls return.

– No Name QA
Nov 26 '18 at 22:34













@NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

– SomeDude
Nov 26 '18 at 22:37





@NoNameQA I don't think the code with recursion is the correct code, for example : int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes); why would you compute the height with next box before computnig height with current box?

– SomeDude
Nov 26 '18 at 22:37













The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

– No Name QA
Nov 26 '18 at 22:39







The code works perfectly. It is not mine. And I don't understand why it works. And this what I'm trying to find out. If you scroll code to the end you will see that it sorts boxes before start do the recursion calls.

– No Name QA
Nov 26 '18 at 22:39















Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

– No Name QA
Nov 27 '18 at 9:39





Your code works incorrectly for the following input: { {7, 3, 8}, {9, 3, 7}, {8, 2, 6}, {6, 4, 4}, {5, 3, 3}, {4, 2, 2} }

– No Name QA
Nov 27 '18 at 9:39













@NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

– SomeDude
Nov 27 '18 at 15:22





@NoNameQA Got it. Thanks for the test. The algorithm should not actually look at longest increasing subsequence, it should calculate increasing subsequence with maximum sum of heights. I updated my answer and also the code. It should work now.

– SomeDude
Nov 27 '18 at 15:22




















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53488279%2ftower-of-the-boxes%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

Calculate evaluation metrics using cross_val_predict sklearn

Insert data from modal to MySQL (multiple modal on website)