S
S
Sarkis Arutiunian2017-10-25 01:20:04
Algorithms
Sarkis Arutiunian, 2017-10-25 01:20:04

How to most efficiently place elements on the square?

Condition of the problem:
We have an area with given proportions, say: The first element in the array is height, the second is width. And we have an array with elements:
const area = [100, 200];

const items = [
[10, 4],
[20, 30],
[25, 3],
...
];

We need a function that will take two arguments, the first area and the second elements: Which will return an object with two arrays:
function resolve(area, items) {...};
console.log(resolve(area, items));
// { solved: [[4, 10], [20, 30], [3, 25]...], exclude: [[50, 60],[2, 100]...]};

The first array includes the maximum number of elements in the correct order and position that can fit in a given area, and the second includes a list of elements that did not fit.
All elements can be flipped by swapping the width and height.
The solution can be in any language or simple math. formula, I will be grateful for any help, thanks!

Answer the question

In order to leave comments, you need to log in

[[+comments_count]] answer(s)
S
Sarkis Arutiunian, 2017-10-25
@sarkis-tlt

I think this is the most accurate solution I've found:
rosettacode.org/wiki/Knapsack_problem

L
longclaps, 2017-10-25
@longclaps

The packing problem has no "math. formula" solution.
Your case is somewhat simpler because of the discreteness.
A normal topic for fl, provided that there is an understanding that optimization problems are not always solved in the best possible way)

A
Alex-1917, 2017-10-25
@alex-1917

Haha, laugh. Although a year ago, when I took on a similar project, I also wore the same rose-colored glasses)))
As a result, the project cost 200k.
The general scheme is as follows:
1. Drive in the coordinates of ALL points of your site into the database, i. 100 * 200 = 20000 points (I had 1000 * 1000)
2. I did it in php - I receive an incoming request for the desired size, for example, I need a 12 * 7 rectangle, I select an array of free points from the database, then I process it in php, there on 300 lines of the script turned out.
3. then return to the database - I mark all points from the selected place with the BUSY mark
, etc.
Of course, you have a fundamentally different task, but the complexity is definitely similar!

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question