Блог пользователя slavik

задача
Автор slavik, 14 лет назад, По-русски
Дано три множества чисел, а также числа p1 и p2. Нужно набрать максимально возможное количество комплектов, чтобы оно удовлетворяло следующим условиям:
1)  Каждый комплект имел ровно три числа, по одному из каждого множества.
2) Сумма чисел должна быть больше p1 и меньше  p2.
Каждое число может принимать участие только в 1 комплекте. 
Размер каждого множества до 100, числа в множествах, а также числа p1 и p2, принадлежат отрезку [-500,500].

Я не уверен, имеет ли эта задача оптимальное решение, работающее за адекватное время,
поэтому желательно находить решение, наиболее близкое к оптимальному.
В силу некоторых причин допускается количество операций до 10^11.
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно решить динамическим программированием за O(L1*L2*L3) - где L1, L2, L3 - размеры множеств.
Пусть D[i][j][k] - максимальное число комплектов которые можно выбрать, если можно брать только комплекты, в которых первый элемент принадлежит первым i элементам первого множества, второй - первым j элементам второго множества, третий - первым k элементам третьего множества.
Тогда D[0][0][0] = 0, а пересчет динамики такой, если p1 <= a[i] + b[j] + c[k] <= p2, то
D[i][j][k] = max(D[i - 1][j - 1][k - 1] + 1, D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1]), иначе
D[i][j][k] = max(D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1]), где a - первое множество, b - второе, c - третье.
Ответ на задачу D[L1][L2][L3]. Вроде правильно :)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    это решение находит только наборы троек такие, что для любых двух из них одна мажорирует другую. Например, оно не работает для 3 множеств {1, 2, 3}, p1 = 5, p2 = 7
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Точно. Как-то не подумал об этом.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот одна из идей, которую я реализовал.(описан алгоритм для положительных элементов множества)
Пусть первое множество a[0..n-1], второе - b[0..m-1],третье - c[0..k-1]
Переберем числа  t1 и t2, 0<=t1<=p1,0<=t2<=p2, t1<=t2. Тогда построим двудольный граф на основе первых двух множеств(по множеству в каждой доле), вершины - числа из множеств, ребро будет проведено между iой и jой вершиной, если t1<a[i]+b[j]<t2.

Найдем максимальное паросочетание в этом графе. Возьмем все ребра, участвующие в макс. паросочетании, и сопоставим каждому ребру сумму чисел на его вершинах. Таким образом, получили массив d[0...x-1]. Теперь аналогично строим граф для множества c и массива d, только теперь между iой и jой вершиной будет проведено ребро, если p1<c[i]+d[j]<p2.
    Находим максимальное паросочетание в этом графе, теперь смотрим, находили ли мы при других значениях t1 и t2 большее паросочетание, если нет, то это является на данный момент ответом.
    Таким образом, решение довольно неплохо работает на случайных тестах за счет перебора t1 и t2. Однако я думаю, что его можно как-то улучшить.
→ Ответить