Сумма или разность чисел в множестве больше или равно числу

Question

У меня есть проблема, которая заявляет следующее:

Учитывая последовательность чисел (S), начальное значение (V) и целевого значения (T), проверьте, есть ли последовательность операций + и -, которые могут быть назначены последовательности S (операции должны соответствовать порядку последовательности), чтобы достичь числа, большего или равного T, начиная с V. Также существует предел X, который нельзя сломать в любое время (если сумма выходит из интервала [0, X] в любое время, этот путь решения недействителен. Все номера в задаче также находятся внутри этого интервала).

Кроме того, я должен найти самую большую сумму, которая может быть получена из этих операций, соблюдая предельные правила (ее можно сломать, если операция -last помещает общую сумму из пределов).

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

Однако я не могу понять, как бороться с лимитирующим правилом и как я могу найти самую большую сумму. Предельная проблема возникает в некоторых ситуациях: предположим, что я пытаюсь найти рюкзачное решение, чтобы найти числа, которые будут добавлены, а остальные числа будут вычтены. Решение рюкзака может сломать верхний предел суммы, но возможно, что фактическая сумма не была бы вызвана порядком операций (она могла бы вычесть что-то до того, как предел будет фактически нарушен, тогда он не будет разбит на все).

Может ли кто-нибудь помочь мне найти меня, чтобы найти хороший подход для этого? Спасибо.

Answer 1

Эта проблема является разновидностью Partition Problem, где один набор - это элементы, которые вы добавляете, а другой - элементы, которые вы выставляете.

Возможное решение Unsurprisingly на основе псевдо-полиномиального решения задачи раздела:

D(V,0) = true 
D(s,0) = false  s != V 
D(s,i) = false s<0 or s > X 
D(s,i) = D(s-arr[i],i-1) OR D(s+arr[i],i-1) 

Вы можете рассчитать рекуррентное соотношение эффективно и строить DP таблицу размеров (X+1)*(n+1).
Когда вы закончите, вы ищете наибольшее значение T<=s<=X в таблице таким образом, чтобы D(s,n) == true