Étant donné un tableau de N entiers, vérifiez s'il est possible d'obtenir une somme de S , en choisissant certains (ou aucun) éléments du tableau et en les ajoutant .
J'ai essayé de résoudre ce problème en utilisant une approche gourmande en triant d'abord le tableau, puis en m'approchant de plus en plus de la somme. Cependant, cela ne fonctionne pas.
Quelqu'un peut-il me dire comment dois-je aborder ce problème?
t = int(input()) for foo in range(t): n = int(input()) arr = list(map(int, input().split())) s = int(input()) sum = 0 for a in range(len(arr)): for b in range(len(arr)-a-1): if(arr[b] > arr[b+1]): temp = arr[b] arr[b] = arr[b+1] arr[b+1] = temp for i in arr: if((sum + i) <= s): sum += i if(sum == s): print("YES") else: print("NO")
3 Réponses :
Une solution de force brute (et sans doute très lente) avec itertools.combinations:
from itertools import combinations
def is_possible_sum(numbers, n):
# One of those rare cases where range() is ok!
for r in range(len(numbers)):
for combo in combinations(numbers, r + 1):
if sum(combo) == n:
return True
return False
La fonction combinaisons renvoie donc une liste de toutes les combinaisons possibles de nombres de taille r.
Merci. Mais je cherchais une solution que je peux coder complètement sans utiliser de fonctions sophistiquées. C'est possible?
Il n'y a rien d'extraordinaire à propos des combinaisons . Il fait partie de la bibliothèque standard.
Vous avez peut-être raison monsieur. Mais puis-je créer cette fonction de combinaisons manuellement?
Je peux regarder les fichiers source pour vérifier comment il est implémenté, non?
@ harshit54: La documentation de intertools.combinations montre à quoi il est à peu près équivalent. Notez que lors de l'écriture du vôtre, vous pourrez peut-être court-circuiter le processus de génération et passer au suivant lorsque la somme partielle dépasse S .
vous vérifiez ce code
# sum using elements of the given array.
def check(arr, N):
ispossible[0] = 1
arr.sort()
for i in range(0, N):
val = arr[i]
# if it is already possible
if ispossible[val]:
continue
# make 1 to all it's next elements
for j in range(0, MAX - val):
if ispossible[j]:
ispossible[j + val] = 1
# Driver code
if __name__ == "__main__":
arr = [2, 3]
N = len(arr)
# maximum size of x
MAX = 1000
# to check whether x is possible or not
ispossible = [0] * MAX
check(arr, N)
x = 7
if ispossible[x]:
print(x, "is possible.")
else:
print(x, "is not possible.")
Solutions dynamiques et combinées et code de test temps / résultats:
Testing function: is_possible_sum_dynamic 0,2630,740 1,7068,5588 2,8120,8725 3,13344,14298 4,22849,24119 5,36515,57237 6,70649,59626 7,83752,86483 8,119746,123067 9,162509,167441 10,217729,263601 11,285210,289287 12,405059,368185 13,461434,462611 14,568958,569770 15,687595,1110547 16,957992,869849 17,998072,1074423 18,1381996,1460914 19,1455941,1399456 20,1803727,1608306 21,1968317,2000050 22,2482750,2602217 23,2737389,2424789 24,2756149,2802634 25,3581139,3282499 26,3360480,3421020 27,3778212,4037443 28,4295289,4182019 29,4850601,4657451 30,5294141,5060018 31,5955458,5811096 32,6386726,6341719 33,6848117,6843303 34,7589508,7485276 35,8231171,8118034 36,8921163,9172343 37,10649931,11339668 38,11922632,11463180 39,12720235,12802786 Testing function: is_possible_sum_combinations 0,3535,880 1,170306,2222 2,5823,1460 3,5944,1441 4,7736,1411 5,11908,1522 6,18459,1565 7,32447,1630 8,59748,1812 9,118461,2062 10,237636,3110 11,495370,3816 12,1007225,4040 13,1945018,3824 14,4091327,6125 15,9028434,6253 16,16549245,5440 17,35843517,5611 18,64125274,5158 19,137040747,5894 20,284994834,6748 21,538974234,5722 22,1108166024,5654 23,2242642192,6019 24,4642429033,6166 25,9368977496,6358 26,18792906166,6285 27,38892974776,6442 28,78689360778,6324 29,160660909206,7009 30,330681016443,7278 31 ,684805660485,10669 32,1361937299206,7018 33
J'ai ajouté la solution de programmation dynamique et modifié le code de DYZ pour éviter un piège évident avec l'appel if_possible_sum_obvious (a, s). La même fonction peut être ajoutée au lieu de deux premières lignes dans la fonction is_possible_sum_dynamic, mais je dois ensuite exécuter à nouveau ce long test et refaire le graphique.
L'axe X est le nombre entier, axe Y - log10 (temps en nanosecondes): 3 = 10 ** 3 ns = 1 μs, 9 = 1 sec, 12 = 1000 sec
Sortie:
# The subset sum problem:
#
# Given an array of N integers, check if it is possible to obtain a sum of S,
# by choosing some (or none) elements of the array and adding them.
#
# The code contributors are Alexander Lopatin, Sahil Shelangia, DYZ
def if_possible_sum_obvious(a, s):
if a is None or len(a) == 0:
return s == 0
if s > 0:
if s > sum([i for i in a if i > 0]):
return False
elif s < 0:
if s < sum([i for i in a if i < 0]):
return False
else:
for i in a:
if i == 0:
return True
else:
return False
return None
def is_possible_sum_dynamic(a, s): # Dynamic Programming
if a is None or len(a) == 0:
return s == 0
n = len(a)
b = [[False for _ in range(s + 1)] for _ in range(n + 1)]
for i in range(n + 1):
b[i][0] = True
for i in range(1, s + 1):
b[0][i] = False
for i in range(1, n + 1):
for j in range(1, s + 1):
if j < a[i - 1]:
b[i][j] = b[i - 1][j]
if j >= a[i - 1]:
b[i][j] = (b[i - 1][j] or b[i - 1][j - a[i - 1]])
return b[n][s]
def is_possible_sum_combinations(a, s): # combinations from itertools
check_obvious = if_possible_sum_obvious(a, s)
if check_obvious is not None:
return check_obvious
from itertools import combinations
for r in range(len(a)):
for combo in combinations(a, r + 1):
if sum(combo) == s:
return True
return False
if __name__ == '__main__':
import time
for f in [is_possible_sum_dynamic, is_possible_sum_combinations]:
print('\nTesting function:', f.__name__)
for N in range(40):
a_global = [i+1 for i in range(N)]
sum2check = sum(a_global)
print(N, end='')
def time_and_check(f_local, sum_local, expected):
t0 = time.perf_counter_ns()
possible = f_local(a_global, sum_local)
t1 = time.perf_counter_ns() - t0
print('', t1, sep=',', end='' if expected else '\n')
if possible != expected:
print('Not possible! Strange')
print(sum_local, a_global, sep='\n')
exit(1)
time_and_check(f, sum2check, True)
time_and_check(f, sum2check + 1, False)
Étant donné un tableau de N éléments : pourquoi avez-vous supposé que N éléments dans un tableau sont tous entiers? Je demanderais: étant donné un tableau de N entiers
@AlexanderLopatin Il a été mentionné dans la question que toutes les entrées seront des nombres entiers.
@ harshit54 Les nombres entiers ne sont pas mentionnés dans la question. Ce problème s'appelle
somme du sous-ensemble@MBo J'ai édité la question pour mentionner les entiers . Merci d'avoir indiqué le nom du problème.
Les éléments ont été changés en entiers il y a une minute ;-) Merci. Question interessante. La solution de force brute proposée par @DYZ a la comlexité O (N!)
@AlexanderLopatin Je suis honnêtement étonné que personne n'ait encore mentionné la solution
O (2 ^ (n / 2)).@ DillonDavis C'est le week-end :-) Voici deux solutions de programmation récursive et dynamique: geeksforgeeks.org/python-program-for-subset-sum-problem-dp-2 5
@dillon Quelle solution O (2 ^ (n / 2))?
@alexander: La solution de DYZ est O (2 ^ N), pas O (N!). (Somme de C (n, i) pour i de 0 à n est 2 ^ n).
@rici est d'accord! Je viens de faire cette découverte en regardant les heures dans la réponse que j'ai publiée il y a 5 minutes :-)
@rici divise le problème en deux - calcule toutes les sommes pour chaque moitié n / 2 du tableau, en
O (2 * 2 ^ (n / 2)) = O (2 ^ (n / 2)) heure. Nécessite un espaceO (2 ^ (n / 2)), mais il existe quelques variantes qui échappent à cela, en utilisant min-heaps (qui ajoutent un facteurlognau temps) , ou en regroupant les sommes des sous-ensembles de chaque moitié.@dillon: mais que faire si la solution n'est pas entièrement contenue dans l'une ou l'autre moitié?
@rici, vous devez vérifier si
targetest contenue dans votre table de hachage, et ajouter un if / check supplémentaire à l'intérieur de votre seconde pour voir si cela correspond à la cible. Ceux-ci expliqueront si son contenu est purement dans l'une ou l'autre moitié. Oublié ça@rici Vous pouvez trouver ces codereview réponses à un problème similaire intéressant. Ils utilisent les techniques auxquelles j'ai fait allusion pour trouver des solutions à l'équivalent d'un problème 4SUM à partir d'un tableau imaginaire contenant tous les nombres entiers.
Ah ok. Oui, cela fonctionnerait.