Mixing
How to calculate maximal square size when fitting N squares in a given container?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Given a container which width is W and height is H, I'd like to fit N squares of maximal size S in it.
Example 1
W = 240
H = 210
N = 7
S = 70
Example 2
W = 200
H = 230
N = 23
S = 40
How would you calculate S from W, H, and N in O(1)?
integer-programming
asked Jul 28 at 4:51
Misha Moroshko
1012
add a comment |Â
up vote
0
down vote
favorite
Given a container which width is W and height is H, I'd like to fit N squares of maximal size S in it.
Example 1
W = 240
H = 210
N = 7
S = 70
Example 2
W = 200
H = 230
N = 23
S = 40
How would you calculate S from W, H, and N in O(1)?
integer-programming
asked Jul 28 at 4:51
Misha Moroshko
1012
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Given a container which width is W and height is H, I'd like to fit N squares of maximal size S in it.
Example 1
W = 240
H = 210
N = 7
S = 70
Example 2
W = 200
H = 230
N = 23
S = 40
How would you calculate S from W, H, and N in O(1)?
integer-programming
asked Jul 28 at 4:51
Misha Moroshko
1012
Given a container which width is W and height is H, I'd like to fit N squares of maximal size S in it.
Example 1
W = 240
H = 210
N = 7
S = 70
Example 2
W = 200
H = 230
N = 23
S = 40
How would you calculate S from W, H, and N in O(1)?
integer-programming
asked Jul 28 at 4:51
Misha Moroshko
1012
asked Jul 28 at 4:51
Misha Moroshko
1012
asked Jul 28 at 4:51
Misha Moroshko
1012
asked Jul 28 at 4:51
Misha Moroshko
1012
1012
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59
add a comment |Â
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
Assume $W ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=sqrtfrac WHN$. If you use that side you get $m=lfloor frac HS rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $frac Hm+3$
Number required in width $n=lceilfrac Nm+3rceil$
Side that fits in width $frac Wn$
Now decrease the number across the height and recompute the sides
It should increase and then start to decrease. Report the maximum.
answered Jul 28 at 5:25
Ross Millikan
275k21185351
It this anO(1)solution? How many checks we need to perform in the worst case before we can stop?
– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Assume $W ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=sqrtfrac WHN$. If you use that side you get $m=lfloor frac HS rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $frac Hm+3$
Number required in width $n=lceilfrac Nm+3rceil$
Side that fits in width $frac Wn$
Now decrease the number across the height and recompute the sides
It should increase and then start to decrease. Report the maximum.
answered Jul 28 at 5:25
Ross Millikan
275k21185351
It this anO(1)solution? How many checks we need to perform in the worst case before we can stop?
– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
add a comment |Â
up vote
0
down vote
Assume $W ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=sqrtfrac WHN$. If you use that side you get $m=lfloor frac HS rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $frac Hm+3$
Number required in width $n=lceilfrac Nm+3rceil$
Side that fits in width $frac Wn$
Now decrease the number across the height and recompute the sides
It should increase and then start to decrease. Report the maximum.
answered Jul 28 at 5:25
Ross Millikan
275k21185351
It this anO(1)solution? How many checks we need to perform in the worst case before we can stop?
– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Assume $W ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=sqrtfrac WHN$. If you use that side you get $m=lfloor frac HS rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $frac Hm+3$
Number required in width $n=lceilfrac Nm+3rceil$
Side that fits in width $frac Wn$
Now decrease the number across the height and recompute the sides
It should increase and then start to decrease. Report the maximum.
answered Jul 28 at 5:25
Ross Millikan
275k21185351
Assume $W ge H$ (otherwise swap them). If you could pack them perfectly the area would say $S=sqrtfrac WHN$. If you use that side you get $m=lfloor frac HS rfloor$ across the height.
Start with $m+3$ (just a guess for safety) across the height, compute
Side that fits in height $frac Hm+3$
Number required in width $n=lceilfrac Nm+3rceil$
Side that fits in width $frac Wn$
Now decrease the number across the height and recompute the sides
It should increase and then start to decrease. Report the maximum.
answered Jul 28 at 5:25
Ross Millikan
275k21185351
answered Jul 28 at 5:25
Ross Millikan
275k21185351
answered Jul 28 at 5:25
Ross Millikan
275k21185351
answered Jul 28 at 5:25
Ross Millikan
275k21185351
275k21185351
It this anO(1)solution? How many checks we need to perform in the worst case before we can stop?
– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
add a comment |Â
It this anO(1)solution? How many checks we need to perform in the worst case before we can stop?
– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
It this an
O(1) solution? How many checks we need to perform in the worst case before we can stop?– Misha Moroshko
Jul 28 at 5:36
It this an
O(1) solution? How many checks we need to perform in the worst case before we can stop?– Misha Moroshko
Jul 28 at 5:36
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
I don't really know. I'm not sure $3$ is enough margin. Probably it is better to start at $frac Hm$ and go both ways until you see a decrease. I haven't figured out a way to bound how many tries you have to make.
– Ross Millikan
Jul 28 at 13:57
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864990%2fhow-to-calculate-maximal-square-size-when-fitting-n-squares-in-a-given-container%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Do the squares have to be axis aligned? That makes it much easier
– Ross Millikan
Jul 28 at 5:05
@RossMillikan Yes!
– Misha Moroshko
Jul 28 at 5:12
Does the original rectangle always have integer dimensions, and do the squares need to have an integer side length?
– prubin
Jul 29 at 21:59