Somme de sous-ensemble avec deux ensembles et cible

Question

Je suis un peu perplexe ici sur la résolution de ce calcul. J'ai réussi à créer un programme de somme de sous-ensembles en utilisant python. Voici le code:

def subsetsum(array,num): 

    if num == 0 or num < 1: 
     return None 
    elif len(array) == 0: 
     return None 
    else: 
     if array[0] == num: 
      return [array[0]] 
     else: 
      with_v = subsetsum(array[1:],(num - array[0])) 
      if with_v: 
       return [array[0]] + with_v 
      else: 
       return subsetsum(array[1:],num) 

Ma question est, si j'ai deux ensembles de tableau à savoir array1 = [4,5,1,7,2,1] et array2 = [7,1,4, 6,3,2] dans lequel la cible est 18 dans un sens où le tableau 1 devrait avoir une cible de 8 et le tableau 2 une cible de 10.

Egalement si j'ai des tableaux qui a une plus grande marge d'erreur. comment pourrais-je le réduire?

Answer 1

Après votre exemple, arr1=[4,5,1,7,2,1], arr2=[7,1,4,6,3,2] et target=18, vous pouvez utiliser un ensemble pour enregistrer la différence entre chaque élément arr1 et la cible, à côté itérer arr2 et vérifier si l'élément est dans l'ensemble, si c'est le cas, vous avez trouvé un numéro dans arr1 et un nombre dans arr2 qui sont additionnés sont égaux à la cible.

def getSubsetSum(arr1, arr2, target): 
    diffs = set() 
    for a in arr1: 
     diffs.add(target - a) 
    for b in arr2: 
     if b in diffs: 
      return (target -b, b) 
    return None