How to find the optimal arrangement of objects in a container?

Question

Algorithms

I don't know how to properly formulate a request for such a task. There is a figure in two-dimensional space, an arbitrary irregular shape, and there are arbitrary figures that need to fill this area as much as possible, with a minimum amount of free space left. Moreover, some of the figures are mandatory, and fill the rest of the space with optional ones to the maximum. All figures, although they have an arbitrary shape, are integral and multiple of pixels. Such a Tetris. There should definitely be something ready already, because the task is trivial and there is no need to reinvent the wheel. Maybe some seamstresses use something like this to cut the canvas with a minimum amount of residue. I would be grateful for a piece of code in any programming language or a ready-made library . 1

is specified at the input
. Container form
2. Shapes of all possible shapes
3. Required shapes and the number of their required copies in the container
The output
is 1. The optimal location of all shapes
Something like this condition

<?php

//Последовательности пикселей
//Отрицательные числа - последовательность пустых пикселей
$input = [
  [3],
  [4],
  [4],
  [4],
  [2],
  [2],
];

$figures = [
  "a" => ,          //Куб
  "b" => ,     //L
  "c" => ,      //J
  "d" => ,               //Линия
  "e" => ,
];

//Обязательные фигуры, с количеством
$require = [
  "a" => 1,   
  "d" => 1,
];

//Фигуры которые используеются для остаточного заполнения
$optional = [
  "a", "b", "c",
];

//Поиск
function search($input, $figures, $require, $optional) {

  //TODO Магия

  return [
    ["b", 0, 0],
    ["a", 1, 0],
    ["c", 3, 1],
    ["d", 0, 3],
    ["a", 0, 4],
  ];
}

print_r(search($input, $figures, $require, $optional));

Answer 1

Fit (in JS: play around ), the most optimal, because it selects through AI, and if you choose the optimal input settings, you can get an extremely good result.
Also, search like this .

Answer 2

Can I throw off the implementation in C for this task? Algorithm NP there is another possibility using the algorithm of dancing links - it will be faster