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

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

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

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

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

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

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


partition-problem algorithm knapsack-problem dynamic-programming
person Haykath    schedule 02.07.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Неудивительно, что возможное решение основано на псевдополиномиальном решении проблемы разбиения:

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

person amit    schedule 02.07.2015