GoldenLine
Zaloguj się

konto usunięte

Temat: Zadanie dla najlepszych

Zadanie brzmi tak.

Mamy zbiór wartości Z zawierający ileś liczb
Mamy wartość W

Znaleść wszystkie podzbiory zbioru Z takie że suma z elementów podzbioru jest równa W.



Innymi słowy:
Z =
{
1
2
3
4
5
5
1
2
}

W = 8

Znaleźć wszystkie kombinacje liczb ze zbioru Z których suma jest równa 8.
Link do wypowiedziLink
Grzegorz Melniczak

Grzegorz Melniczak Have you tried
turning it off and
on again?

Temat: Zadanie dla najlepszych

A = pusty -- w A przechowujemy listę podzbiorów
dla każdego podzbioru B zbioru Z {
jeżeli suma_elementów_podzbioru_B = W to dodaj B do A
}

złożoność niestety wykładnicza, ale w końcu to problem NP:)
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

To jasne, w pytaniu chodziło o to jak to ogarnąć w excelu, w szczególności jak wygenerować wszystkie podzbiory zeby po nich przelupować i sprawdzić czy suma się zgadza.

Ale dzięki;)
Link do wypowiedziLink
Grzegorz Melniczak

Grzegorz Melniczak Have you tried
turning it off and
on again?

Temat: Zadanie dla najlepszych

Wszsystkich podzbiorów jest 2^n gdzie n to liczba elementów zadanego zbioru. Jeżeli sobie ten zbiór uporządkujemy na końcu (nie ważne jak - po prostu nadamy każdemu elementowi liczbę porządkową od 0 do n-1), dalej tworzymy wektor charakterystyczny podzbioru i otrzymamy bijekcję pomiędzy wszystkimi podzbiorami a liczbami całkowitymi od 0 do 2^n-1
np:
mamy dany {a,b,c,d}, n=4
przyporządkujmy a=0, b=1, c=2, d=3
i mamy wtedy:
{} = (0,0,0,0) = 0*2^0 + 0*2^1 + 0*2^2 + 0*2^3 = 0
{a,c} = (1,0,1,0) = 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3 = 5
{a,b,c,d} = (1,1,1,1) = 1*2^0 + 1*2^1 + 1*2^2 + 1*2^3 = 15

aby z liczb odzyskać podzbiory należy liczby przedstawić w zapisie binarnym

G.
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Nic nie kumam ale na szczęście temat już ogarnięty.
Link do wypowiedziLink
Darek S.

Darek S. _

Temat: Zadanie dla najlepszych

Henryk Kutypera:
Nic nie kumam ale na szczęście temat już ogarnięty.

Wez sie podzieeeel!
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Temat jest ogarnięty na poziomie organizacyjnym tzn. ten algorytm przestał być potrzebny;)
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy





Wyślij zaproszenie do
Anuluj