How to solve box stacking problem with single instance of box

Revision en2, by servesh196, 2018-07-23 13:17:15

I started solving standard DP problem. I found this problem here is the link, . 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.

Tags #dynamic-programming, box-satcking


  Rev. Lang. By When Δ Comment
en2 English servesh196 2018-07-23 13:17:15 2 Tiny change: 'g-problem/.I have alr' -> 'g-problem/ . I have alr'
en1 English servesh196 2018-07-23 13:12:41 1181 Initial revision (published)