Максимально возможная сумма кратных
Как бы вы решили это?
У вас есть 2 массива, каждый с n цифрами, n <= 500. Вы можете выбрать один номер из
первые три в первом массиве и умножить его на первое число в
второй массив. Продолжайте делать это, пока не будет использован каждый номер. Написать
максимально возможная сумма этих кратных.
Например:
n = 4;
first array contains : 16 6 2 10
second array contains : 3 8 12 9
Output : 336
Для первого числа из второго массива — 3 — вы можете выбрать из 16,6 и
2. Лучший вариант — выбрать 2. Сумма теперь 3 * 2 = 6;
Для второго числа из второго массива — 8 — вы можете выбрать из 16,6,10 (номер 2
уже использован). Лучший вариант — выбрать 6. Добавьте 8 * 6 к сумме, так что сумма
сейчас 54.
Для третьего числа из второго массива — 12 вы можете выбрать из
16,10 (номера 2 и 6 уже используются). Лучший вариант — выбрать 16.
Добавьте к сумме 12 * 16, чтобы сумма составила 246.
За последний номер со второго
массив — 9 — вы можете выбрать только 10. Добавьте 9 * 10 к сумме, поэтому сумма сейчас
336.
У меня было мало идей, но каждая из них была не права. Например, я попытался отсортировать оба массива, а затем умножить наибольшее число во втором массиве на максимально возможное число в первом массиве (потому что 1. число во втором массиве может выбирать только из 1. -3. Позиция в первом массиве, второе число может выбирать только от 1.-4 и т. д.), но это не так. Также у меня есть еще несколько решений, но мне сложно их объяснить, потому что я не знаю, как выразить это по-английски (но я мог бы опубликовать код и попытаться объяснить его), и они также не правы.
РЕДАКТИРОВАТЬ: Я нашел несколько алгоритмов, которые могут быть решением для моей проблемы. Во-первых Венгерский алгоритм, второй Аукционный алгоритм. Это мой первый контакт с линейным программированием … Я понимаю, как работает венгерский алгоритм, но я не могу его реализовать. В алгоритме аукциона я даже не уверен, как он работает. Кроме того, я не знаю, достаточно ли они быстры. Временная сложность венгерского алгоритма составляет O (n ^ 3), и я в моем случае n <= 500, поэтому для максимального значения n это может длиться слишком долго. Также в Задача назначения каждый «работник» может выполнять любую «работу», но в моем случае это не так.
Это может быть Максимальная проблема потока,но я не уверен в этом, потому что мне нужно идеальное соответствие — это означает, что каждая вершина совпадает — и я не знаю, гарантируется ли это этим алгоритмом.
Решение
Во-первых, для меня не ясно, почему для первого числа из второго массива мы должны использовать только три первых элемента из первого массива, а для каждого другого числа из второго массива мы используем любые числа из первого массива.
Однако мы можем представить эти два массива в виде двудольного графа, где каждое число из второго массива соединяется с (каждым? *) Числами из первого массива. В этом графе каждое ребро (u, v) имеет вес, равный умножению двух чисел из массивов (u * v).
И для данного графика вы должны решить проблема максимального потока.
* если я правильно понимаю проблему, вы должны соединить первое число из 2-го массива с первыми 3 числами из 1-го массива, и каждое другое число из 2-го массива с каждым числом из 1-го массива.
Другие решения
Продолжайте делать это, пока не будет использован каждый номер. Напишите максимально возможную сумму этих кратных
Это похоже на дискретную и комбинаторную задачу оптимизации. Этот первый алгоритм, который пришел мне в голову, чтобы решить это с помощью Ветвь и Связка алгоритм.
Это позволяет отслеживать назад, и вы можете реализовать его с помощью рекурсии.
Я реализовал подход смешанного целочисленного программирования в Юля с помощью Прыгать. Это работает для вашего примера, и общая концепция должна работать, но может потребоваться дополнительное тестирование!
Это должно быть вполне читабельно, даже если вы не знакомы с Джулией. Имейте в виду, что индексирование начинается с 1 (как в Matlab) вместо 0 (как в C, Java, …)
Основная идея заключается в следующем (прочитайте комментарии, чтобы понять больше): определите двоичную переменную X с размерностью (N, N): если X [a, b] == 1 -> A [b] было выбрано на шаге a.
Самое сложное для понимания — это BigM-Formulation, который просто другая формулировка логики объяснил в комментариях. Это единственная цель линеаризующая!
using JuMP
N = 4
A = [16 6 2 10]
B = [3 8 12 9]
# MODEL
m = Model()
# VARS
@defVar(m, x[1:N, 1:N], Bin) # N steps, N vars/indices // binary
# CONSTRAINTS
# (1) exactly one var chosen in each step
for s = 1:N
@addConstraint(m, sum(x[s,:]) == 1)
end
# (2) each var is chosen exactly once
for v = 1:N
@addConstraint(m, sum(x[:,v]) == 1)
end
# (3) if var v chosen in step s -> are enough predecessors already taken away -> is in positions 1:3?
for s = 1:N
for v = 1:N
needed_pops_before = v - 3
if needed_pops_before > 0
# bigM formulation:
# formula: (x[s,v] == 1) -> sum of predecessors taken away until now >= needed_pops
# use deMorgan-law -> !(x[s,v] == 1) -> sum >= needed_pops
# formulate with bigM = N because needed_pops limited by N-3
@addConstraint(m, N * (1-x[s,v]) + sum{x[ss,jj], ss=1:s-1, jj=1:v-1} >= needed_pops_before)
end
end
end
# OBJECTIVE
@setObjective(m, Max, sum{B[s] * A[v] * x[s,v], s=1:N, v=1:N})
# SOLVE
status = solve(m)
# OUTPUT
println("Objective is: ", getObjectiveValue(m))
println("Solution: ")
for s = 1:N
for v = 1:N
if getValue(x[s,v]) > 0.00001
print(A[v], " ")
end
end
end
Выход:
Objective is: 336.0
Solution:
2 6 16 10