Блог пользователя servesh196

Автор servesh196, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)