There is a set of pictures of the same height and different width, and there is a container of a certain width, into which these pictures should be combined with the minimum total error as follows:
enter image description here
Gray are images, red is error. Principle: pictures consistently fill the line with some indentation, and if the next picture goes beyond the width of the container, then it comes from a new line, the unused width of the previous (or last) line is an error. It is necessary to find such a sequence of pictures so that the total error is minimal.

  • one
    Ha, now the brain will train, even interesting. - Digital Core
  • @DigitalCore, the task arose as an application (to combine the manufacturers' logos in the online store), but it is similar to the Olympiad, and it can only be a complete search. - user239133
  • 2
    Should logos take turns or randomly? - Digital Core
  • @DigitalCore, in that order (probably, there may be a lot of sequences), at which the error is minimal. They need to sort out, in principle. - user239133
  • 2
    en.wikipedia.org/wiki/Bin_packing_problem - jfs

1 answer 1

At Oscar I do not pretend, the code in C # (label any-language).

  1. generate 200 images of fixed height, and of arbitrary length.
  2. add to List<images>
  3. sorted by image length
  4. Determine whether the image of the largest size fits in the string
  5. Determine whether the smallest image is placed in the string
 using System; using System.Collections.Generic; using System.Data; using System.Drawing; using System.Linq; using System.Windows.Forms; namespace Sort_Picture_In_block { public partial class FormMain : Form { private List<Images> l = new List<Images>(); private int m = 1000; // максимальная длинна строки в пикселях private int p = 10; // расстояние между изображениями class Images { public Images(int width, Image image) { this.width = width; this.image = image; } public int width { get; set; } public Image image { get; set; } } public FormMain() { InitializeComponent(); } private void btnSort_Click(object sender, EventArgs e) { SortImages(); } private void Form1_Load(object sender, EventArgs e) { Random rend = new Random(); for (int i = 0; i < 200; i++) { int w = rend.Next(50, 250); Image bmp = new Bitmap(w, 50); Graphics g = Graphics.FromImage(bmp); Color color = Color.Black; Rectangle rectangle = new Rectangle(0, 0, w - 1, bmp.Height - 1); g.DrawRectangle(new Pen(color), rectangle); l.Add(new Images(w, bmp)); } l = l.OrderBy(images => images.width).ToList(); } private void SortImages() { while(l.Count > 0) { int s = 0; int i = 0; while (s + p < m && l.Count() > 0) { if (m - (s += p) > l[l.Count() - 1].width) { Image img = l[l.Count() - 1].image; l.Remove(l[l.Count() - 1]); s += img.Width; // пишем картинку в строку ... i++; } if (l.Count() > 0 && m - s > l[0].width) { Image img = l[0].image; l.Remove(l[0]); s += img.Width; // пишем картинку в строку ... i++; } else { txtLog.Text += $"Длинна строки = {s} px, картинок {i} шт. \r\n"; s = m; } } } } } }

enter image description here