When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

servesh196's blog

By servesh196, history, 6 years ago, In English

I started solving standard DP problem. I found this problem here is the link, https://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/ . I have already solved this problem. Now in this problem we have infinite instance of single box so we can use any rotation of a particular box. so, this problem with little variation what if we can use only one instance of box. How to solve this problem I tried to figure out solution myself but I am not getting the idea how to solve ??. Brute force solution won't work here complexity of brute force solution would be 4^n.

Each box can have six different rotation in which pair of two will have same base area so for each box we have total 3+1 choice 1 for not selecting particular box . so, complexity will be 4*4*…..n-times. I also tried the same way as standard problem can be solved with slight difference in implementation but I am getting wrong answer. I am not asking this question without trying enough. I have spent many days in this problem. I also tried to google if i can get any hint.

Any suggestion or hint would be helpful, Thank You.

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess the approach can be like defining the state for each box like lxb b×h h×l. If these three states are kept then we can check the transition states for the next possible combinations using next box. Its just a guess. I am unable to give the complete solution. Hope some red coder gives us the solution :)