Problem sumy podzbioru (liczba podzbiorów)

0

Cześć,
muszę napisać algorytm który obliczy ile jest możliwych podzbiorów podanego zbioru N dwuelementowego tak aby suma tego podzbioru była równą S. (S podane) No czyli problem sumy podzbioru. Na internecie jest dużo rozwiązań tego problemu, większość taka sama tzn tworzymy tablice N x S no i tablica[i][j] jest równa 1 jeśli za pomocą elementów od 0 do i da się wygenerować sumę = j. (Tak to przynajmniej rozumiem)

  1. Z tym że potrzebuje wiedzieć ( a tego już nie znalazłem) jak z tej tablicy teraz wyciągnąć informacje o tym ile jest takich podzbiorów które dają ta sumę?
  2. Oraz nie wiem jak zmodyfikować rozwiązanie aby działało tez dla elementów < 0 ?
    Dzięki za każdą pomoc.
1

Generalnie problem jest NP. Ale można próbować, jest rozwiązanie rekurencyjne, nie wiem jaki język, więc daję Python (kompilowalny pseudokod:)):

k = 0

def number_of_subsets(num_set, target_sum, array_part = []):
	s = sum(array_part)
	if s == target_sum:
		global k
		k += 1
	if s >= target_sum:
		return 
	for i in range(len(num_set)):
		n = num_set[i]
		rest = num_set[i+1:]
		number_of_subsets(rest, target_sum, array_part + [n])


number_of_subsets([1, 2, 3, 4 ,5], 4)
print(k) # -> 2

Idea jest taka: jak częściowa suma jest równa to jakoś to zaznaczamy (ja wybrałem modyfikację zmiennej globalnej, mozna też drukować wynik, albo użyć yield). Jak jest większa to return - wiadomo; a potem oddzielamy jeden element, bierzemy resztę, a element oddzielony dodajemy do listy częściowej.
W ten sposób rekurencja, magicznie:), wygeneruje nam wszystkie podzbiory, a początek algorytmu odfiltruje właściwe.
Nie wien czy to zadziała dla ujemnych.

0

Co ma być dwuelementowe? Jak podzbiory to sortujesz, i dla kolejnych liczb szukasz binarnie czy jest S minus ta liczba. Jak N dwuelementowe zgodnie z tym co napisałeś to siłą rzeczy albo zero albo jeden.

0
sig napisał(a):

Co ma być dwuelementowe? Jak podzbiory to sortujesz, i dla kolejnych liczb szukasz binarnie czy jest S minus ta liczba. Jak N dwuelementowe zgodnie z tym co napisałeś to siłą rzeczy albo zero albo jeden.

Przepraszam, chciałem napisac n - elementowego ale źle napisałem i "poprawiło" mi na dwuelementowego. Przepraszam za wprowadzenie w bład

0
lion137 napisał(a):

Generalnie problem jest NP. Ale można próbować, jest rozwiązanie rekurencyjne, nie wiem jaki język, więc daję Python (kompilowalny pseudokod:)):

k = 0

def number_of_subsets(num_set, target_sum, array_part = []):
	s = sum(array_part)
	if s == target_sum:
		global k
		k += 1
	if s >= target_sum:
		return 
	for i in range(len(num_set)):
		n = num_set[i]
		rest = num_set[i+1:]
		number_of_subsets(rest, target_sum, array_part + [n])


number_of_subsets([1, 2, 3, 4 ,5], 4)
print(k) # -> 2

Idea jest taka: jak częściowa suma jest równa to jakoś to zaznaczamy (ja wybrałem modyfikację zmiennej globalnej, mozna też drukować wynik, albo użyć yield). Jak jest większa to return - wiadomo; a potem oddzielamy jeden element, bierzemy resztę, a element oddzielony dodajemy do listy częściowej.
W ten sposób rekurencja, magicznie:), wygeneruje nam wszystkie podzbiory, a początek algorytmu odfiltruje właściwe.
Nie wien czy to zadziała dla ujemnych.

Dzieki,
zapomniałem napisac ze w jezyku C, ale w sumie algorytm mi wystarczy. Tak myslałem własnie nad podobnym rozwiązaniem. Napisałeś że problem jest NP tzn mowisz o problemie wyznaczenia LICZBY podzbiorow tak? bo problem wyznaczenia czy taki podzbior istnieje to chyba nie jest NP? (uzywajac na przyklad tej tablicy 2d ?).

0

Również to czy taki podzbiór istnieje też jest NP, generalnie, nie znamy lepszego sposobu na znalezienie, danego podzbioru, jak sprawdzać wszystkie, a na to nie znamy algorytmu wielomianowego.

0
lion137 napisał(a):

Również to czy taki podzbiór istnieje też jest NP, generalnie, nie znamy lepszego sposobu na znalezienie, danego podzbioru, jak sprawdzać wszystkie, a na to nie znamy algorytmu wielomianowego.

Jak pisałem o tej tablicy 2d to chodziło mi o cos takiego:

1

To rozwiązanie, można nazwać pseudo wielomianowym, (ma sporo przypadków gdzie jest dość szybkie). Coś takiego jak metoda rezolucji w rachunku zdań, złożoność ciągle wykładnicza, ale dla wielu zadań daje przyzwoity czas.

0
lion137 napisał(a):

To rozwiązanie, można nazwać pseudo wielomianowym, (ma sporo przypadków gdzie jest dość szybkie). Coś takiego jak metoda rezolucji w rachunku zdań, złożoność ciągle wykładnicza, ale dla wielu zadań daje przyzwoity czas.

Dlaczego wykładnicza? W sensie mamy N x S tablice i dla kazdej komorki sprawdzamyu komórkę nad nią oraz komórke nad nią i w lewo o iles tam znakow. czyli (N x S x 2) ? (Pewnie czegos nie zauważam)

1 użytkowników online, w tym zalogowanych: 0, gości: 1