Еще один вариант PARTITION

13

У меня сведение следующей проблемы с разделом к ​​определенной проблеме планирования:

Входные данные: список целых положительных чисел в неубывающем порядке.a1an

Вопрос: существует ли вектор такой, что(x1,,xn){1,1}n

k i = 1 a i x i0

Σязнак равно1NaяИксязнак равно0и
Σязнак равно1КaяИкся0для всех К{1,...,N}

Без второго условия это просто РАЗДЕЛЕНИЕ, следовательно, NP-hard. Но второе условие, кажется, дает много дополнительной информации. Мне интересно, есть ли эффективный способ решить этот вариант. Или это все еще сложно?

Томас Калиновский
источник

Ответы:

15

Вот сокращение от PARTITION к этой проблеме. Пусть (a1,...,aN) будет экземпляром PARTITION. Предположим, что a1a2aN .

Пусть будет «очень большим числом», например, . Рассмотрим экземпляр нашей проблемы.NNзнак равно(Σязнак равно1N|aя|)+1

N,...,N5N раз,N+a1,...,N+aN,4N,...,4NN раз
  1. Если существует решение для PARTITION, то - это решение нашей проблемы.Икс1,...,ИксN

    1,...,14N раз,-Икс1,...,-ИксN,Икс1,...,ИксN,-1,...,-1N раз
  2. Если есть решение экземпляра нашей проблемы (к которому мы сократили экземпляр PARTITION), то . Таким образом, То есть является решением для PARTITION.(Икс1,...,Икс5N,Y1,...,YN,Z1,...,ZN)Σязнак равно1NaяYя0(модификацияN)

    Σязнак равно1NaяYязнак равно0.
    (Y1,...,YN)
Юрий
источник
Спасибо Юрий. В моем приложении важно, чтобы список входов упорядочивался не по убыванию, а вход в вашем сокращении - нет. Я изменю вопрос, чтобы сделать требование заказа более явным. (N,a1,...,aN,N)
Томас Калиновский
@thomas: я этого не заметил. Теперь я обновил свое решение.
Юрий