Выделение чисел (x1, x2, x3, ...) каждому элементу в списке (a1, a2, a3, ...) так, чтобы a1 / x1 был похож на a2 / x2 и т. Д.

Question

Предположим, у меня есть список чисел = [3, 10, 20, 1, ...] Как можно назначить число (x1, x2, x3, x4, ...) каждому из элементов в списке, чтобы 3 / x1 ~ = 10 / x2 ~ = 20 / x3 ~ = 1 / x4 =. ..?

Редактировать: есть некоторые ограничения на числа (x1, x2, x3 ...). они должны быть выбраны из списка доступных чисел (которые также могут быть числами с плавающей запятой). Проблема в том, что количество элементов не одинаково. Есть еще X элементов. Х могут быть назначены несколько раз.

Цель состоит в том, чтобы минимизировать разницу между 3 / x1, 10 / x2, 20 / x3, 1 / x4

Answer 1

Часто помогает разработать математическую модель. Э.Г.

Пусть

   a(i)>=0  i=1,..,m
   b(j)>0   j=1,..,n with n > m

быть данными.

Ввести переменные (определяется моделью)

   c      =  common number for all expressions to be close to
   x(i,j) =  1 if a(i) is assigned to b(j)
             0 otherwise  

Тогда мы можем написать:

min sum((i,j), (x(i,j)*(a(i)/b(j) - c))^2 )
subject to
    sum(j, x(i,j)) = 1   for all i  (each a(i) is assigned to exactly one b(j))
    x(i,j) in {0,1}
    c free

Это нелинейная модель. Решатели MINLP (Смешанное целочисленное нелинейное программирование) легко доступны. Вы также можете выбрать цель, которая может быть линеаризована:

min sum((i,j), abs(x(i,j)*(a(i)/b(j) - y(i,j))) )
subject to
    y(i,j) = x(i,j)*c
    sum(j, x(i,j)) = 1   for all i
    x(i,j) in {0,1}
    c free

Это можно переформулировать как модель MIP (смешанного целочисленного программирования). Есть много доступных MIP-решателей.

Решение может выглядеть так:

Значения внутри матрицы: a (i) / b (j). Каждая строка соответствует a (i) и имеет ровно одно совпадение b (j).

Подробнее здесь .