Продажа блоков временных интервалов

27

Учитывая временных интервалов, которые хотят купить k человек. Человек i имеет значение h ( i , j ) 0 для каждого временного интервала j . Каждый человек может купить только один последовательный блок временных интервалов, который может быть пустым.nkih(i,j)0j

Существует ли алгоритм полиномиального времени для расчета максимального значения, которого может достичь продавец?

Без ограничения последовательности мы можем дать каждому временному интервалу человека, который ценит его больше всего. Кроме того, если мы фиксируем порядок временных интервалов людей, то динамическое программирование может использоваться для определения максимального значения первых 0 i k людей, покупающих первые 0 j n временных интервалов.k0ik0jn

user11550
источник

Ответы:

9

Для 3CNF с предложениями по переменным x 1 , , x n . Предположим, что x i и ¯ x i появляются в формуле не более k i раз соответственно.ϕ1,,ϕkx1,,xnxixi¯ki

Мы разрабатываем цветной DAG , вершины которого состоят из трех частей:G

  • "Назначение" вершины и ˉ v я ( J ) , 1 я N , 1 J K I . Цвет v я ( J ) с "цветом" х I ( J ) , и ˉ v я ( J ) с ¯ х я ( J ) .vi(j)v¯i(j)1in1jkivi(j)xi(j)v¯i(j)xi¯(j)
  • Вершины «пункта» , 1 i k , j = 1 , 2 , 3 . Цвет ж я ' ( J ' ) с цветом х I ( J ) (или ¯ х я ( J ) ) , если ¯ х я (или х I , соотв.) Является J 'wi(j)1ikj=1,2,3wi(j)xi(j)xi¯(j)xi¯xij-ый литерал предложения , и это j-й оператор, содержащий этот литерал.ϕij
  • «Вырезать» вершины . Раскрасьте их разными цветами, отличными от приведенных выше.s=s0,s1,,sn,sn+1,sn+k=t

Края включают в себя:

  • , v i ( j ) v i ( j + 1 ) , v i ( k i ) s i ;si1vi(1)vi(j)vi(j+1)vi(ki)si
  • , ˉ v я ( J ) ˉ v я ( J + 1 ) , ˉ v я ( K I ) Š я ;si1v¯i(1)v¯i(j)v¯i(j+1)v¯i(ki)si
  • и , w i ( j ) s n + i .sn+i1wi(j)wi(j)sn+i

Так , например, из 3CNF следующий график строится (Краевые направления слева направо). (x1x2x3¯)(x1x2¯x3)введите описание изображения здесь

Теперь нетрудно видеть, что исходная 3CNF выполнима тогда и только тогда, когда в G существует путь - t с разными цветами вершин .stG

(Кстати, побочным продуктом является то, что существование - t пути с разными цветами вершин в цветном DAG является NP-трудным . Я не нашел много литературы по этой проблеме в вычислительной перспективе. Если вы знаете, пожалуйста, комментарий!)stNP-hard

Так, какова связь между и проблемой OP? Интуитивно понятно, что мы собираемся сделать, это спроектировать матрицу h , чтобы каждый цвет отображался в строке (которая является человеком), а края - в последовательные столбцы (временные интервалы). Следовательно, максимальное планирование, которое в основном происходит слева направо в матрице, соответствует s - t пути.Ghst

Наша матрица имеет 2 n + 1 + i 2 k i + k столбцов с индексами, начинающимися с 0 . В следующем constrcution X Y два значения удовлетворяют 1 « X « Y . Отношения X / 1 , Y / X могут быть большими степенями k и n . Пусть K i = 2 i + 2 i jh2n+1+i2ki+k0XY1XYX/1,Y/Xkn.Ki=2i+2j=1iki

  • Для каждого , 0 i n , пусть h ( s i , K i ) = h ( s i , K i - k i - 1 ) = h ( s i , K i + k i + 1 + 1 ) = Y (если координата существует, то же самое ниже).si0inh(si,Ki)=h(si,Kiki1)=h(si,Ki+ki+1+1)=Y
  • Для каждого пусть h ( x i ( j ) , K i - 1 + j ) = X ; Для каждого ¯ х я ( J ) , пусть ч ( ¯ х я ( J ) , К я - 1 + K я + 1 + J ) = Х .xi(j)h(xi(j),Ki1+j)=Xxi¯(j)h(xi¯(j),Ki1+ki+1+j)=X
  • Для каждого , 1 i k и литерала x в предложении ϕ i , пусть h ( x , K n + i ) = 1 .ϕi1ikxϕih(x,Kn+i)=1
  • Все остальные записи равны 0.

Например, для приведенного выше примера графика соответствующая матрица введите описание изображения здесь

Теперь мы утверждаем: исходное 3CNF выполнимо тогда и только тогда, когда максимальное значение равно .(2n+1)Y+ikiX+k

Рассмотрим планирование достижения максимального значения. Поскольку в h есть ровно столбцов, содержащих Y , все они должны быть покрыты. Для столбца K i + k i + 1, который имеет два варианта выбора Y , предположим, что планирование назначает его для s i . Поскольку столбец K i должен быть присвоен s i , по последовательности мы должны потерять столбцы K i + 1 до K i + k(2n+1)hYKi+ki+1YsiKisiKi+1 . То же самое происходит, если планирование назначает столбец K i + k i + 1 для s i + 1 .Ki+kiKi+ki+1si+1

Поэтому, чтобы иметь значение , мы должны выбрать все остальные доступные X в матрице, что соответствует назначению на переменные. Таким образом, остальное значение k достижимо тогда и только тогда, когда присваивание удовлетворяет каждому условию.ikiXXk

В заключение, решение о максимальной стоимости юридического планирования в . Может быть, поэтому все наши предыдущие попытки найти алгоритм потерпели неудачу.NP-hard

Виллард Жан
источник
Но, в примере матрицы, если я выбрать ¯ х 2 и х 3 я все еще может попасть в цель. Что я делаю не так? Кроме того , Х в ¯ х 1 ( 1 ) должен быть один столбец вправо и Х в ¯ х 1 ( 2 ) должна быть одна колонка слеваx1¯ x2¯x3Xx1¯(1)Xx1¯(2)
rotia
@rotia Да, и это означает на левой стороне вы должны выбрать , чтобы иметь 4 X . Так что это соответствует удовлетворяющему назначению x 1 = x 2 = 1 , x 3 = 0 . x1,x2,x3¯4Xx1=x2=1,x3=0
Уиллард Жан
Можете ли вы уточнить , что «Пусть больше один в два числа появлений литералов х I и ¯ х я .» средства? Каков номер появления литерала? Это то, где оно появляется в пунктах / формуле, или сколько раз оно встречается в формуле? Является ли K я буквальным или номер? kixixi¯ki
DW
@DW это число. Мое выражение было действительно совсем не ясно; Я редактировал это. ki
Уиллард Жан
@WillardZhan Да. Но если я выберу эти переменные, я могу получить значение, которое больше, чем в формуле. Например, я устанавливаю и X = 7 , в соответствии с формулой я должен получить только 450 баллов (при условии, что k - это количество предложений). Но, выбирая х 1 , х 2 , ¯ х 3 я могу получить до 452 пунктов, выбирая четыре из них справаY=60X=7kx1,x2,x3¯
rotia
3

Это решение имеет проблемы и будет удалено в ближайшее время; см. комментарий templatetypedef.

Вы можете решить это за полиномиальное время, используя поток минимальных затрат . В дальнейшем все ребра имеют единичную емкость.

  • Создайте исходную вершину и целевую вершину t . Мы отправим k единиц потока от s до t .stkst
  • Создайте вершин v 0 , , v n, чтобы представить моменты времени между слотами, и направленный край v j v j + 1 для каждого 0 j < n со стоимостью 0.n+1v0,,vnvjvj+10j<n
  • i
    • siti
    • 0j<nsivjΣk=1jh(i,k)j=0
    • 1jnvjtiΣk=1jh(i,k)
    • ssi
    • tit

isitisitiisivjvktikjvk=jiij+1,,k

sj+1,,kv

h(i,j)

j_random_hacker
источник
3
i
ississ1tittkttisi+1M1i<kMk1
k
i>ij<jji
sivjsii