0

我有一个问题，说明如下：

给定一个数字序列 (S)、一个初始值 (V) 和一个目标值 (T)，检查是否存在可以分配给序列 S 的 + 和 - 操作序列（这些操作必须遵守序列顺序) 达到一个大于或等于 T 的数，从 V 开始。此外，有一个极限 X 不能在任何时候被打破（如果总和在任何时候离开区间 [0, X]，则该解决方案路径无效。问题中的所有数字也在这个区间内）。

此外，我必须找到可以从这些操作中获得的最大总和，遵守限制规则（如果 -last- 操作使总和超出限制，则可能会被破坏）。

我一直在研究它，并研究了一些关于背包问题和分区问题的动态规划解决方案，我相信解决方案会是这一行。

但是我不知道如何处理限制规则以及如何找到最大的总和。在某些情况下会出现极限问题：假设我试图找到一个背包解决方案来找到要相加的数字，其余的数字要减去。背包解决方案可以打破总和的上限，但实际总和可能不会因为操作的顺序（它可以在限制实际被打破之前减去一些东西，那么它就不会被打破全部）。

任何人都可以帮我找到一个好的方法吗？谢谢你。

4

1 回答 1

1

这个问题是分区问题的变体，其中一组是您添加的元素，另一组是您减去的元素。

不出所料，可能的解决方案是基于分区问题的伪多项式解决方案：

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

于 2015-07-02T12:17:03.390 回答