Pack rectangular objects of different sizes in a fixed size rectangle
If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for.
I have a rectangular space.
I also have a number of rectangle objects.
I want to find an algorithm that will try to fit all the objects in the rectangle and if this is not possible I want to know that so that I can show an error message.
This is for a computer program that I am working with to place images on a sheet of paper so that I can print them. The idea is to waste as little paper as possible.
Edit: Found this one which was a very interesting read: http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
Makes me realise that there really is not a simple answer to this problem
geometry algorithms packing-problem
add a comment |
If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for.
I have a rectangular space.
I also have a number of rectangle objects.
I want to find an algorithm that will try to fit all the objects in the rectangle and if this is not possible I want to know that so that I can show an error message.
This is for a computer program that I am working with to place images on a sheet of paper so that I can print them. The idea is to waste as little paper as possible.
Edit: Found this one which was a very interesting read: http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
Makes me realise that there really is not a simple answer to this problem
geometry algorithms packing-problem
1
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
2
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20
add a comment |
If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for.
I have a rectangular space.
I also have a number of rectangle objects.
I want to find an algorithm that will try to fit all the objects in the rectangle and if this is not possible I want to know that so that I can show an error message.
This is for a computer program that I am working with to place images on a sheet of paper so that I can print them. The idea is to waste as little paper as possible.
Edit: Found this one which was a very interesting read: http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
Makes me realise that there really is not a simple answer to this problem
geometry algorithms packing-problem
If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for.
I have a rectangular space.
I also have a number of rectangle objects.
I want to find an algorithm that will try to fit all the objects in the rectangle and if this is not possible I want to know that so that I can show an error message.
This is for a computer program that I am working with to place images on a sheet of paper so that I can print them. The idea is to waste as little paper as possible.
Edit: Found this one which was a very interesting read: http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html
Makes me realise that there really is not a simple answer to this problem
geometry algorithms packing-problem
geometry algorithms packing-problem
edited Mar 5 '18 at 6:54
J. M. is not a mathematician
60.9k5150289
60.9k5150289
asked Aug 8 '14 at 19:19
www.jensolsson.sewww.jensolsson.se
14113
14113
1
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
2
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20
add a comment |
1
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
2
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20
1
1
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
2
2
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20
add a comment |
3 Answers
3
active
oldest
votes
If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.
Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
add a comment |
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $Ssetminus A$ such that $sum_{xin A} x=sum_{xin Ssetminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.
add a comment |
The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.
You can offer, for example, the following sorting criteria:
1) total area (use for the upper left corner of the area)
2) the largest linear size;
3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).
The number of objects placed is small, so the issues of theoretical optimality should not be major.
Good luck!
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f891437%2fpack-rectangular-objects-of-different-sizes-in-a-fixed-size-rectangle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.
Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
add a comment |
If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.
Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
add a comment |
If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.
Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.
If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.
Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.
answered Aug 8 '14 at 19:38
user2566092user2566092
21.5k1946
21.5k1946
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
add a comment |
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper?
– www.jensolsson.se
Aug 9 '14 at 8:22
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
@www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search
– user2566092
Aug 9 '14 at 17:46
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
Well, that is the problem, I really cannot change the paper size.
– www.jensolsson.se
Aug 12 '14 at 6:58
add a comment |
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $Ssetminus A$ such that $sum_{xin A} x=sum_{xin Ssetminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.
add a comment |
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $Ssetminus A$ such that $sum_{xin A} x=sum_{xin Ssetminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.
add a comment |
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $Ssetminus A$ such that $sum_{xin A} x=sum_{xin Ssetminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $Ssetminus A$ such that $sum_{xin A} x=sum_{xin Ssetminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.
answered Dec 2 '18 at 16:40
Alex RavskyAlex Ravsky
39.4k32181
39.4k32181
add a comment |
add a comment |
The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.
You can offer, for example, the following sorting criteria:
1) total area (use for the upper left corner of the area)
2) the largest linear size;
3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).
The number of objects placed is small, so the issues of theoretical optimality should not be major.
Good luck!
add a comment |
The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.
You can offer, for example, the following sorting criteria:
1) total area (use for the upper left corner of the area)
2) the largest linear size;
3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).
The number of objects placed is small, so the issues of theoretical optimality should not be major.
Good luck!
add a comment |
The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.
You can offer, for example, the following sorting criteria:
1) total area (use for the upper left corner of the area)
2) the largest linear size;
3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).
The number of objects placed is small, so the issues of theoretical optimality should not be major.
Good luck!
The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.
You can offer, for example, the following sorting criteria:
1) total area (use for the upper left corner of the area)
2) the largest linear size;
3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).
The number of objects placed is small, so the issues of theoretical optimality should not be major.
Good luck!
answered Dec 6 '18 at 22:40
Yuri NegometyanovYuri Negometyanov
11k1728
11k1728
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%2f891437%2fpack-rectangular-objects-of-different-sizes-in-a-fixed-size-rectangle%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
1
You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here.
– user2566092
Aug 8 '14 at 19:47
2
Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg
– DanielV
Jan 7 '17 at 5:05
It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said.
– hardmath
Jul 19 '17 at 5:20