Zielsummenalgorithmus mit Numpy ⇐ Python

[Guest]

Ich habe eine Reihe von Schwimmern und eine Zielsumme. Ich versuche, alle möglichen Kombinationen von Elementen zu finden, die zur Zielsumme addieren würden. /p>
Einschränkungen: < /p>

• Der gleiche Wert kann im Array mehrmals angezeigt werden. < /li>
  < li>

  Code: Select all

  0 < array.size < 1000000

• Code: Select all

  0  List[Tuple[float, ...]]:
  
  arr = np.asarray(arr, dtype=np.float64)
  n = len(arr)
  
  # HM to store combinations Key: Sum, Value: indices
  dp = defaultdict(set)
  
  # Convert sum to int
  def get_sum_key(value: float) -> int:
  return int(round(value / epsilon))
  
  # Add all individual elements
  for i, num in enumerate(arr):
  dp[get_sum_key(num)].add((i,))
  
  result = []
  
  # Combining each new number with all existing combinations
  for i in range(n):
  curr_num = arr[i]
  # Make a copy of current sums to avoid modifying while iterating
  current_sums = list(dp.items())
  
  for sum_key, combinations in current_sums:
  new_sum = sum_key * epsilon + curr_num
  new_sum_key = get_sum_key(new_sum)
  
  # Add new combination
  for comb in combinations:
  # Check to ensure no duplicate indices
  if i > max(comb):
  new_comb = comb + (i,)
  dp[new_sum_key].add(new_comb)
  
  # Check for target sum
  if (abs(new_sum - target) < epsilon and
  len(new_comb) >= min_elements):
  result.append(tuple(float(arr[idx]) for idx in new_comb))
  
  return sorted(result, key=len)
  
  arr=generate_random_array(size=20, min_val=1000, max_val=100000, seed=42)
  target_sum=arr[1]+arr[2]+arr[4]+arr[5]
  
  combinations = find_target_sum_combinations(arr, target_sum)
  print(f"\nCombinations that sum to {target_sum}:")
  for comb in combinations:
  print(f"{comb} = {sum(comb)}")