Fitting smaller rectangles into bigger
$begingroup$
I need to fit following rectangles into one big rectangle of N" * 72".
Length * width - No of rectangles of this dimension
20" * 18" - 4 count.
12" * 12" - 6 count.
24" * 6" - 2 count.
20" * 8" - 2 count.
16" * 12" - 6 count.
8" * 10 " - 4 count.
12" * 6" - 4 count.
12" * 8" - 4 count.
12" * 10" - 4 count.
10" * 6" - 10 count.
we can have a few rectangles little bigger to make it fit in a complete rectangle. If given a choice, I would prefer a haphazard configuration. Can anyone please help us ?
Thanks
packing-problem
asked Aug 15 '16 at 15:50
N JainN Jain
11
$endgroup$
add a comment |
$begingroup$
I need to fit following rectangles into one big rectangle of N" * 72".
Length * width - No of rectangles of this dimension
20" * 18" - 4 count.
12" * 12" - 6 count.
24" * 6" - 2 count.
20" * 8" - 2 count.
16" * 12" - 6 count.
8" * 10 " - 4 count.
12" * 6" - 4 count.
12" * 8" - 4 count.
12" * 10" - 4 count.
10" * 6" - 10 count.
we can have a few rectangles little bigger to make it fit in a complete rectangle. If given a choice, I would prefer a haphazard configuration. Can anyone please help us ?
Thanks
packing-problem
asked Aug 15 '16 at 15:50
N JainN Jain
11
$endgroup$
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55
add a comment |
$begingroup$
I need to fit following rectangles into one big rectangle of N" * 72".
Length * width - No of rectangles of this dimension
20" * 18" - 4 count.
12" * 12" - 6 count.
24" * 6" - 2 count.
20" * 8" - 2 count.
16" * 12" - 6 count.
8" * 10 " - 4 count.
12" * 6" - 4 count.
12" * 8" - 4 count.
12" * 10" - 4 count.
10" * 6" - 10 count.
we can have a few rectangles little bigger to make it fit in a complete rectangle. If given a choice, I would prefer a haphazard configuration. Can anyone please help us ?
Thanks
packing-problem
asked Aug 15 '16 at 15:50
N JainN Jain
11
$endgroup$
I need to fit following rectangles into one big rectangle of N" * 72".
Length * width - No of rectangles of this dimension
20" * 18" - 4 count.
12" * 12" - 6 count.
24" * 6" - 2 count.
20" * 8" - 2 count.
16" * 12" - 6 count.
8" * 10 " - 4 count.
12" * 6" - 4 count.
12" * 8" - 4 count.
12" * 10" - 4 count.
10" * 6" - 10 count.
we can have a few rectangles little bigger to make it fit in a complete rectangle. If given a choice, I would prefer a haphazard configuration. Can anyone please help us ?
Thanks
packing-problem
packing-problem
asked Aug 15 '16 at 15:50
N JainN Jain
11
asked Aug 15 '16 at 15:50
N JainN Jain
11
edited Aug 15 '16 at 15:53
N Jain
asked Aug 15 '16 at 15:50
N JainN Jain
11
asked Aug 15 '16 at 15:50
N JainN Jain
11
asked Aug 15 '16 at 15:50
N JainN Jain
11
11
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55
add a comment |
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There are three observations one can make about your set of rectangles.
- Their total area is $6136$.
- The width of them are all even integers.
- Except the ten rectangles with dimension $10 times 6$, the width of the rest are multiples of $4$.
If you are going to pack the rectangle so that they
are axis-aligned and don't allow them to rotate,
then using $(1)$ and $(2)$, one can show that
$$N ge 2 leftlceil frac12 times frac{6136}{72}rightrceil = 86$$
If more than two of the ten rectangles with dimension $10 times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 times 72$ rectangle.
In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.
$hspace1in$ 
We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.
If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution,
there are commercial software which does the job.
If you want to learn how to do that yourself, look at answers of this
related question on stackoverflow as a start.
edited May 23 '17 at 12:39
Community♦
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1893097%2ffitting-smaller-rectangles-into-bigger%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are three observations one can make about your set of rectangles.
- Their total area is $6136$.
- The width of them are all even integers.
- Except the ten rectangles with dimension $10 times 6$, the width of the rest are multiples of $4$.
If you are going to pack the rectangle so that they
are axis-aligned and don't allow them to rotate,
then using $(1)$ and $(2)$, one can show that
$$N ge 2 leftlceil frac12 times frac{6136}{72}rightrceil = 86$$
If more than two of the ten rectangles with dimension $10 times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 times 72$ rectangle.
In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.
$hspace1in$
We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.
If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution,
there are commercial software which does the job.
If you want to learn how to do that yourself, look at answers of this
related question on stackoverflow as a start.
edited May 23 '17 at 12:39
Community♦
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
$endgroup$
add a comment |
$begingroup$
There are three observations one can make about your set of rectangles.
- Their total area is $6136$.
- The width of them are all even integers.
- Except the ten rectangles with dimension $10 times 6$, the width of the rest are multiples of $4$.
If you are going to pack the rectangle so that they
are axis-aligned and don't allow them to rotate,
then using $(1)$ and $(2)$, one can show that
$$N ge 2 leftlceil frac12 times frac{6136}{72}rightrceil = 86$$
If more than two of the ten rectangles with dimension $10 times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 times 72$ rectangle.
In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.
$hspace1in$
We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.
If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution,
there are commercial software which does the job.
If you want to learn how to do that yourself, look at answers of this
related question on stackoverflow as a start.
edited May 23 '17 at 12:39
Community♦
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
$endgroup$
add a comment |
$begingroup$
There are three observations one can make about your set of rectangles.
- Their total area is $6136$.
- The width of them are all even integers.
- Except the ten rectangles with dimension $10 times 6$, the width of the rest are multiples of $4$.
If you are going to pack the rectangle so that they
are axis-aligned and don't allow them to rotate,
then using $(1)$ and $(2)$, one can show that
$$N ge 2 leftlceil frac12 times frac{6136}{72}rightrceil = 86$$
If more than two of the ten rectangles with dimension $10 times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 times 72$ rectangle.
In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.
$hspace1in$
We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.
If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution,
there are commercial software which does the job.
If you want to learn how to do that yourself, look at answers of this
related question on stackoverflow as a start.
edited May 23 '17 at 12:39
Community♦
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
$endgroup$
There are three observations one can make about your set of rectangles.
- Their total area is $6136$.
- The width of them are all even integers.
- Except the ten rectangles with dimension $10 times 6$, the width of the rest are multiples of $4$.
If you are going to pack the rectangle so that they
are axis-aligned and don't allow them to rotate,
then using $(1)$ and $(2)$, one can show that
$$N ge 2 leftlceil frac12 times frac{6136}{72}rightrceil = 86$$
If more than two of the ten rectangles with dimension $10 times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 times 72$ rectangle.
In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.
$hspace1in$
We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.
If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution,
there are commercial software which does the job.
If you want to learn how to do that yourself, look at answers of this
related question on stackoverflow as a start.
edited May 23 '17 at 12:39
Community♦
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
edited May 23 '17 at 12:39
Community♦
1
edited May 23 '17 at 12:39
Community♦
1
edited May 23 '17 at 12:39
Community♦
1
1
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
answered Aug 19 '16 at 14:15
achille huiachille hui
96.6k5132261
96.6k5132261
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1893097%2ffitting-smaller-rectangles-into-bigger%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Have you even tried to pack them? Note that dimensions can be divided by two to make things easier.
$endgroup$
– Parcly Taxel
Aug 15 '16 at 16:13
$begingroup$
Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones?
$endgroup$
– Moti
Aug 15 '16 at 16:54
$begingroup$
i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles
$endgroup$
– N Jain
Aug 15 '16 at 17:55