[已解决]有没有什么办法可以让一串数中的任意几项加和等于指定数

zc4555666

如题。给定了一串数，我需要将一串无序的数导入，然后给定指定数，当数据加和等于给定数时，返回加和的数据。

最佳答案

月排行榜 / 总排行榜

陶远航

2023-5-12 11:36:14

这是一个经典的问题，也叫“子集和问题”。可以使用回溯法来解决这个问题。

具体来说，每次递归调用时，我们考虑两种情况：将当前数字加入结果列表（即路径），或者不将其加入。然后逐步枚举所有情况，直到找到了一个和等于给定数的序列。

下面是一个使用回溯法解决子集和问题的示例代码（假设要求的总和为target_sum，数字序列为nums）：

1. def find_sum(nums, target_sum):
   
2.     result = []
   
3.     current_path = []
   
4. 
   
5.     def backtrack(start, current_sum):
   
6.         if current_sum == target_sum:   # 如果当前和等于目标和，添加当前路径至结果列表中
   
7.             result.append(current_path[:])
   
8.             return
   
9. 
   
10.         for i in range(start, len(nums)):
    
11.             num = nums[i]
    
12.             if current_sum + num > target_sum:   # 如果当前和加上当前数字已超过目标和，则不继续向下搜索
    
13.                 continue
    
14.             current_path.append(num)    # 尝试将当前数字加入当前路径
    
15.             backtrack(i + 1, current_sum + num)   # 继续向下搜索
    
16.             current_path.pop()    # 回溯到上一层
    
17. 
    
18.     backtrack(0, 0)   # 从第0个数字开始搜索
    
19. 
    
20.     return result   # 返回满足条件的路径列表
    

复制代码

这个函数会返回一个列表，其中包含所有和等于目标和的组合。例如，如果nums=[2, 5, 3, 1, 4]，target_sum=7，则会返回[[2, 5], [3, 4]].

跳转到最佳答案楼层

陶远航

这是一个经典的问题，也叫“子集和问题”。可以使用回溯法来解决这个问题。

具体来说，每次递归调用时，我们考虑两种情况：将当前数字加入结果列表（即路径），或者不将其加入。然后逐步枚举所有情况，直到找到了一个和等于给定数的序列。

下面是一个使用回溯法解决子集和问题的示例代码（假设要求的总和为target_sum，数字序列为nums）：

1. def find_sum(nums, target_sum):
   
2.     result = []
   
3.     current_path = []
   
4. 
   
5.     def backtrack(start, current_sum):
   
6.         if current_sum == target_sum:   # 如果当前和等于目标和，添加当前路径至结果列表中
   
7.             result.append(current_path[:])
   
8.             return
   
9. 
   
10.         for i in range(start, len(nums)):
    
11.             num = nums[i]
    
12.             if current_sum + num > target_sum:   # 如果当前和加上当前数字已超过目标和，则不继续向下搜索
    
13.                 continue
    
14.             current_path.append(num)    # 尝试将当前数字加入当前路径
    
15.             backtrack(i + 1, current_sum + num)   # 继续向下搜索
    
16.             current_path.pop()    # 回溯到上一层
    
17. 
    
18.     backtrack(0, 0)   # 从第0个数字开始搜索
    
19. 
    
20.     return result   # 返回满足条件的路径列表
    

复制代码

这个函数会返回一个列表，其中包含所有和等于目标和的组合。例如，如果nums=[2, 5, 3, 1, 4]，target_sum=7，则会返回[[2, 5], [3, 4]].

isdkz

您可以使用回溯算法来解决此问题。具体来说，您可以编写一个函数，该函数将输入列表以及目标和作为参数，并尝试找到一个子集，其总和等于目标和。以下是一个可能的实现：

1. def find_subset(nums, target):
2.     def backtrack(start, target, path):
3.         if target == 0:
4.             return path
5.         if target < 0:
6.             return None
7.         for i in range(start, len(nums)):
8.             result = backtrack(i+1, target-nums[ i], path+[nums[ i]])
9.             if result:
10.                 return result
11.         return None
12.    
13.     return backtrack(0, target, [])

复制代码

在这个实现中， backtrack  函数采用三个参数：起始索引  start ，目标和  target  和当前路径  path 。该函数首先检查当前的目标和是否为零，如果是，则返回当前路径，表示找到了一个子集。如果目标和小于零，则返回  None ，表示当前路径不是解决方案。否则，该函数尝试从起始索引开始迭代列表中的每个元素。对于每个元素，它递归调用  backtrack  函数，将其索引加一，并将目标和减去该元素的值。如果递归调用返回一个解决方案，则  backtrack  函数返回该解决方案。如果没有找到解决方案，则返回  None 。

您可以将上述函数用于解决您的问题，如下所示：

1. nums = [3, 1, 4, 2, 5, 8]
2. target = 9
3. result = find_subset(nums, target)
4. print(result)

复制代码

在这个示例中，输入列表是  [3, 1, 4, 2, 5, 8] ，目标和是  9 。运行  find_subset  函数后，它将返回一个子集，其总和等于  9 。在这种情况下，可能的子集是  [3, 1, 5]  或  [4, 5] ，因为它们的总和都是  9 。

zc4555666

isdkz 发表于 2023-5-12 11:37
您可以使用回溯算法来解决此问题。具体来说，您可以编写一个函数，该函数将输入列表以及目标和作为参数，并 ...

但是我的数据是浮点数，如果用Decimal来运算的话应该在哪个地方添加？而且这个只能返回一个值，如果想返回所有值的数组应该怎么做？

zc4555666

陶远航 发表于 2023-5-12 11:36
这是一个经典的问题，也叫“子集和问题”。可以使用回溯法来解决这个问题。

具体来说，每次递归调用时， ...

你好，这个怎么修改才能进行准确的浮点数运算呢

陶远航

zc4555666 发表于 2023-5-13 15:29
你好，这个怎么修改才能进行准确的浮点数运算呢

当涉及浮点数时，应该使用一个小误差范围（例如1e-9）来检查当前和是否接近于目标和，而不是直接比较它们是否相等。例如，可以将以下行：

1. if current_sum == target_sum:

复制代码

替换为：

1. if abs(current_sum - target_sum) < 1e-9:

复制代码

此外，在计算当前和时，也应该使用浮点数，如下所示：

1. if abs(current_sum + num - target_sum) < 1e-9:   # 如果当前和加上当前数字已接近目标和

复制代码

这样修改后，函数应该能够进行准确的浮点数运算。