#algorithm #combinations
#алгоритм #комбинации
Вопрос:
Итак, у меня есть 12 списков, и каждый из них содержит 28 элементов со значением.
Я пытаюсь максимизировать значение первого списка, переключая элементы с другими 11 списками.
Я также могу торговать разным количеством предметов. Например, я могу обменять 6 товаров из списка 1 и 3 товара из списка 2. Или я могу обменять 19 товаров из списка 1 и 22 товара из списка 2. В большом пуле есть другие элементы, которые не являются частью списка, поэтому, если список содержит более 28 элементов, самые низкие значения могут быть легко удалены, а если в списке меньше 28 элементов, то можно легко добавить новые элементы.
Однако одно ограничение заключается в том, что я могу торговать только с одним списком одновременно. Например, я не могу обменять 3 элемента из списка 1 на список 2, обменять 3 элемента из списка 2 на список 3 и обменять 3 элемента из списка 3 на список 1. Когда я торгую из первого списка, я могу торговать только с одним другим списком одновременно.
Я, очевидно, могу использовать грубую силу, но я чувствую, что это займет целую вечность. Я не силен в комбинациях, поэтому я не совсем уверен, сколько было бы разных комбинаций, если бы я хотел использовать грубую силу.
Итак, мои вопросы таковы: является ли грубое принуждение возможным решением здесь, и если нет, то какой пример алгоритма, который мог бы мне помочь?
Спасибо, Krzys.
Редактировать:
Пример:
List 1
[Apple - 12]
[Banana - 5]
[Orange - 8]
List 2
[Steak - 15]
[Chicken - 2]
[Fish - 7]
List 3
[Zebra - 20]
[Horse - 6]
[Elephant - 10]
Итак, я начну со списка 1. Это то, что будет делать программа:
if (List1.Apple - List2.Steak < BestTradeAvailable) Then BestTradeAvailable = List1.Apple - List2.Steak
if (list1.Apple - List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Apple - List2.Chicken
if (list1.Apple - list2.Fish < BestTradeAvailable) Then BestTradeAvailable = list1.Apple - list2.Fish
if (list1.Banana - List2.Steak < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Steak
if (list1.Banana - List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Chicken
if (list1.Banana - List2.Fish < BestTradeAvailable) Then BestTradeAvailable = list1.Banana - List2.Fish
и т. д
Я также хочу выполнять несколько элементов одновременно, поэтому:
if (list1.Apple list1.Banana - List2.Steak List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = list1.Apple list1.Banana - List2.Steak List2.Chicken
Но, как я уже говорил, вы можете обменять один элемент из списка 1 и 2 элемента из списка 2:
if (list1.Apple - List2.Steak List2.Chicken < BestTradeAvailable) Then BestTradeAvailable = List1.Apple - List2.Steak List2.Chicken
Итак, в принципе, я просто хочу попробовать найти лучшую доступную сделку.
В этом примере лучшей сделкой будет обмен яблока апельсина на List3 на зебру и слона, потому что эта сделка увеличивает общую стоимость List1 на наибольшую сумму.
Комментарии:
1. Этот вопрос невозможно понять. Приведите для нас небольшой пример, скажем, с четырьмя списками, каждый из которых содержит четыре элемента, демонстрируя, какое количество вы пытаетесь максимизировать.
2. @EricLippert Я поработаю над примером.
3. Итак, в вашем примере, какая сделка является лучшей? Какой результат вы ожидаете от программы в этом случае и почему?
4. Лучшей сделкой будет обмен яблока апельсина на List3 на зебру и слона, потому что эта сделка увеличивает общую стоимость List1 на наибольшую сумму.
5. Почему яблоко / апельсин для зебры / слона работают лучше, чем банан / апельсин для зебры / слона?
Ответ №1:
По сути, вам нужно отсортировать списки и выбрать 28 лучших?
Очереди с приоритетом будут работать.
Ответ №2:
Решение методом грубой силы потребует только O (n ^ 2 * (m-1)) временной сложности, где n — количество элементов в списке, а m — количество списков. Если вы хотите искать все комбинации, это будет O (n ^ 2 * (n-1) * (m-1)) временная сложность, которая будет составлять всего 232848 комбинаций, которые вы должны попробовать. Или все комбинации равны n! если порядок тоже важен.
Комментарии:
1. Вы уверены? Из того, что я сделал сам, используя nCr, если бы я выбирал 10 игроков из 28, которых я рассматривал для торговли с другими командами, количество комбинаций, которые я могу составить с 10 игроками из 28, которые у меня есть, равно 28C10, что равно 13123110…
2. Вы сказали, что хотите максимизировать компромисс, поэтому вам не нужно добавлять порядок элементов к комбинациям. 28 ^ 10 верно, когда порядок тоже важен.
3. Подождите, я думал, что nCr предназначен исключительно для комбинаций, в то время как nPr — это порядок элементов? Если нет, и ваш ответ правильный, то я определенно просто закончу грубым форсированием этого.