How to solve box stacking problem with single instance of box

Правка en1, от servesh196, 2018-07-23 13:12:41

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.

Теги #dynamic-programming, box-satcking

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский servesh196 2018-07-23 13:17:15 2 Tiny change: 'g-problem/.I have alr' -> 'g-problem/ . I have alr'
en1 Английский servesh196 2018-07-23 13:12:41 1181 Initial revision (published)