大于或等于某个数的集合中的数之和或差
Sum or difference of numbers in a set greater or equal to a number
我的问题如下：
给定一个数字序列 (S)、一个初始值 (V) 和一个目标值 (T)，检查是否存在可以分配给序列 S 的 + 和 - 操作序列（操作必须遵守顺序）以达到大于或等于T的数字，从V开始。另外，有一个限制X不能在任何时候被打破（如果总和在任何时候退出区间[0，X]，即解法路径无效，题中所有数字也在该区间内）。
此外，我必须找到可以从这些操作中获得的最大和，遵守限制规则（如果 -last- 操作使总和超出限制，则可以打破）。
我一直在研究它并研究了一些关于背包问题和分区问题的动态规划解决方案，我相信解决方案会在这一行中。
但是我不知道如何处理限制规则以及如何找到最大的和。在某些情况下会出现极限问题：假设我试图找到一个背包解决方案来找到将被添加的数字，而其余的数字将被减去。背包解决方案可能会突破总和的上限，但由于操作顺序的原因，实际总和可能不会（它可能会在实际突破限制之前减去一些东西，然后它不会被打破全部）。
任何人都可以帮我找到一个好的方法吗？
谢谢。
此问题是 Partition Problem 的变体，其中一组是您添加的元素，另一组是您减去的元素。
一个可能的解决方案不出所料是基于分区问题的伪多项式解决方案：
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 table 大小 (X+1)*(n+1)。
完成后，您正在寻找 table 中的最大值 T<=s<=X 使得 D(s,n) == true
我的问题如下：
给定一个数字序列 (S)、一个初始值 (V) 和一个目标值 (T)，检查是否存在可以分配给序列 S 的 + 和 - 操作序列（操作必须遵守顺序）以达到大于或等于T的数字，从V开始。另外，有一个限制X不能在任何时候被打破（如果总和在任何时候退出区间[0，X]，即解法路径无效，题中所有数字也在该区间内）。
此外，我必须找到可以从这些操作中获得的最大和，遵守限制规则（如果 -last- 操作使总和超出限制，则可以打破）。
我一直在研究它并研究了一些关于背包问题和分区问题的动态规划解决方案，我相信解决方案会在这一行中。
但是我不知道如何处理限制规则以及如何找到最大的和。在某些情况下会出现极限问题：假设我试图找到一个背包解决方案来找到将被添加的数字，而其余的数字将被减去。背包解决方案可能会突破总和的上限，但由于操作顺序的原因，实际总和可能不会（它可能会在实际突破限制之前减去一些东西，然后它不会被打破全部）。
任何人都可以帮我找到一个好的方法吗？ 谢谢。
此问题是 Partition Problem 的变体，其中一组是您添加的元素，另一组是您减去的元素。
一个可能的解决方案不出所料是基于分区问题的伪多项式解决方案：
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 table 大小 (X+1)*(n+1)。
完成后，您正在寻找 table 中的最大值 T<=s<=X 使得 D(s,n) == true