当元素可以为零时，目标和 dp 算法

Question

目标求和提示：

You are given a set of positive numbers and a target sum ‘S’. Each number should be assigned either a ‘+’ or ‘-’ sign. We need to find the total ways to assign symbols to make the sum of the numbers equal to the target ‘S’.
Input: {1, 1, 2, 3}, S=1
Output: 3
Explanation: The given set has '3' ways to make a sum of '1': {+1-1-2+3} & {-1+1-2+3} & {+1+1+2-3}

假设"Sum(s1("表示集合">

s1"的总和，"Sum(s2("表示集合"s2"的总和。添加negative sign以设置"s2">

这个方程可以简化为子集和问题target + sum(nums)/2

sum(s1) - sum(s2) = target
sum(s1) + sum(s2) = sum(nums)
2 * sum(s1) = target + sum(nums)
sum(s1) = target + sum(nums) / 2

def findTargetSumWays(nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if (sum(nums) + S) % 2 == 1 or sum(nums) < S:
return 0
ssum = (sum(nums) + S) // 2
dp = [[0 for _ in range(ssum + 1)] for _ in range(len(nums))]
# col == 0
for i in range(len(nums)):
# [] or [0]
if i == 0 and nums[i] == 0:
dp[i][0] = 2
# [] or [0] from previous
elif nums[i] == 0:
dp[i][0] = 2 * dp[i-1][0]
else:  # empty set only
dp[i][0] = 1
# take 1st element nums[0] in s == nums[0]
for s in range(1, ssum + 1):
if nums[0] == s:
dp[0][s] = 1
for i in range(1, len(nums)):
for s in range(1, ssum + 1):
if nums[i] != 0:
# skip element at i
dp[i][s] = dp[i - 1][s]
# include element at i
if s >= nums[i]:
dp[i][s] += dp[i - 1][s - nums[i]]
else: # nums[i] = 0
dp[i][s] = dp[i-1][s] * 2
return dp[len(nums) - 1][ssum]

我在这个提示上花了几个小时，但仍然无法通过以下示例

[7,0,3,9,9,9,1,7,2,3]
6
expected: 50
output: 43 (using my algorithm)

我也在这里查看了其他人的答案，它们都是有道理的，但我只想知道我在这里的算法中可能错过了哪里？

Answer 1

你可以这样做：

from itertools import product
def findTargetSumWays(nums, S):
a = [1,-1]
result=[np.multiply(nums,i) for i in list(product(a, repeat=len(nums))) if sum(np.multiply(nums,i))==S]
return(len(result))
findTargetSumWays(inputs,6)
50

基本上，我在元组中获得了 -1,1 的所有可能组合，其大小与输入元素相同，然后将这些元组与输入相乘。

Answer 2

我在处理零时遇到了同样的问题，但我在单独处理零的C++上这样做了。

确保在背包方法中跳过零，即

if(a[i-1] == 0)
dp[i][j] = dp[i-1][j];

我们可以通过简单地计算零出现来单独处理零，我们可以将它们放在 S1 或 S2 中。因此，对于每个零，它是 2*(答案(，对于 n 个零，它是 2^n * (答案(，即

answer = pow(2, num_zero) * answer;

另外，如果 sum(nums( + target 是奇数，因为 S1 不能是分数或目标大于 sum(nums(，不要忘记简单地返回零，即

if(sum < target || (sum+target)%2 == 1)
return 0; 

整体代码如下所示：

int subsetSum(int a[], int n, int sum) {
int dp[n+1][sum+1];


for(int i = 0; i<sum+1; i++)
dp[0][i] = 0;

for(int i = 0; i<n+1; i++)
dp[i][0] = 1;

for(int i = 1; i<n+1; i++) {
for(int j = 1; j<sum+1; j++) {

if(a[i-1] == 0)
dp[i][j] = dp[i-1][j];

else if(a[i-1]<=j)
dp[i][j] = dp[i-1][j-a[i-1]] + dp[i-1][j];

else
dp[i][j] = dp[i-1][j];
}
}

return dp[n][sum]; }

int findTargetSumWays(int a[], int target) {

int sum = 0;
int num_zero = 0;

for(int i = 0; i<a.size(); i++) {
sum += a[i];
if(a[i] == 0)
num_zero++;
}

if(sum < target || (sum+target)%2 == 1)
return 0;

int ans = subsetSum(a, a.size(), (sum + target)/2);
return pow(2, num_zero) * ans;
}

Answer 3

问题的根源是这部分，初始化 col == 0：

# col == 0
for i in range(len(nums)):
# [] or [0]
if i == 0 and nums[i] == 0:
dp[i][0] = 2
# [] or [0] from previous
elif nums[i] == 0:
dp[i][0] = 2 * dp[i-1][0]
else:  # empty set only
dp[i][0] = 1

此代码根据列表的排序方式以不同的方式处理零(如果命中非零值，它将值重置为 1(。它应该看起来像这样：

# col == 0
for i in range(len(nums)):
# [] or [0]
if i == 0 and nums[i] == 0:
dp[i][0] = 2
elif i == 0:
dp[i][0] = 1
# [] or [0] from previous
elif nums[i] == 0:
dp[i][0] = 2 * dp[i-1][0]
else:  # empty set only
dp[i][0] = dp[i - 1][0]

这样，第一个值将设置为 2 或 1，具体取决于它是否为零，并且列表中后面的非零值不会将该值重置为 1。这将在您的示例案例中输出 50。

您还可以通过提供更简单的初始条件来消除错误空间：

def findTargetSumWays(nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
if (sum(nums) + S) % 2 == 1 or sum(nums) < S:
return 0
ssum = (sum(nums) + S) // 2
dp = [[0 for _ in range(ssum + 1)] for _ in range(len(nums) + 1)]
# col == 0
dp[0][0] = 1
for i in range(len(nums)):
for s in range(ssum + 1):
dp[i + 1][s] = dp[i][s]
if s >= nums[i]:
dp[i + 1][s] += dp[i][s - nums[i]]
return dp[len(nums)][ssum]

这会在添加任何数字之前添加一个额外的行来表示状态(左上角只有一个 1(，并在其余行上运行您的算法。您不需要初始化任何其他内容或以不同的方式处理零，这样应该更容易推理代码。

Answer 4

函数的问题与管理列表中零值的方式有关。也许处理零值的更简单方法是将它们从流程中排除，然后将结果计数乘以 2**Z，其中 Z 是零值的数量。

在尝试查找问题时，我对你的代码做了一些简化，最终得到这个：(它给出了正确的答案，即使列表中有零(。

ssum  = (sum(nums) + S) // 2 
dp    = [1]+[0]*ssum         # number of sets that produce each sum from 0 to ssum
for num in nums:        
for s in reversed(range(num,ssum + 1)):
dp[s] += dp[s-num]
return dp[ssum]

我所做的是：

• 消除dp中的维度，因为您不需要保留所有先前的设置计数。 只有当前和下一个。实际上，如果您将总和值从ssum向下处理到零(我做到了(，它只能使用当前集计数工作。
• 通过从当前num值开始s范围来消除条件s >= nums[i]，以便索引s - num永远不会为负数。
• 完成此操作后，就不需要nums索引，我可以直接浏览值。
• 然后，我通过将零和初始化 1 的dp来摆脱零值的所有特殊条件(即最初空集是获得零和的一个解决方案，然后从那里开始增量(。
• 从空集基线开始，允许逐步累积设定计数，为所有值生成正确的结果，而无需对零进行任何特殊处理。当num为零时，自然会将所有当前设置计数加倍，因为dp[s] += dp[s-0]与dp[s] = 2 * dp[s]相同。如果列表以零开头，则零 (dp[0]( 之和的集合计数将加倍，并且所有后续num值将具有更大的起始计数(因为它们从空集用 1 初始化的dp[0]值开始(。
• 通过最后一次更改，函数开始给出正确的结果。

我的断言是，由于您的解决方案不是从"空集"基线开始的，因此零处理逻辑干扰了集合计数的自然进展。我没有尝试微调零条件，因为它们不是必需的，让它们达到与"提前一步"初始化会产生的相同状态似乎毫无意义

从那里，可以通过避免分配超出最小和最大可能总和的范围来进一步优化逻辑dp[s](当我们浏览nums列表时，它会向前"滑动"(：

ssum   = (sum(nums) + S) // 2 
dp     = [1]+[0]*ssum
maxSum = 0
minSum = S - ssum   # equivalent to: ssum - sum(nums)
for num in nums:
maxSum += num
minSum += num
for s in reversed(range(max(num,minSum),min(ssum,maxSum)+1)):
dp[s] += dp[s-num]
return dp[ssum]