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

konto usunięte

Temat: Zadanie dla najlepszych

Poniższy program w Haskellu:
import Data.List



main = do

  putStrLn $ show wynik

  where

    liczby = [1, 2, 3, 4, 5, 5, 1, 2]

    suma   = 8

    wynik  = filter ((== 8) . sum) $ subsequences liczby

daje w wyniku:
[[1,3,4],[1,2,5],[3,5],[1,2,5],[3,5],[1,2,4,1],[3,4,1],[2,5,1],[2,5,1],[1,2,3,2],[2,4,2],[1,5,2],[1,5,2],[2,3,1,2],[1,4,1,2],[5,1,2],[5,1,2]]

Powyższa lista zawiera powtórzenia i uwzględnia kolejność elementów, ale sądzę, że mając ją można bez problemu doprowadzić ją do pożądanej postaci.Grzegorz N. edytował(a) ten post dnia 08.12.09 o godzinie 20:16
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Οἶδα οὐδὲν εἰδώςWojciech Błoński edytował(a) ten post dnia 09.12.09 o godzinie 05:09
Link do wypowiedziLink
Karol Nowacki

Karol Nowacki Programista PHP,
Perl, C,
administrator
systemów *NIX

Temat: Zadanie dla najlepszych

Klasyka:
http://en.wikipedia.org/wiki/Subset_sum_problem
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Przecież to problem NP-zupełny. Wygląda zresztą jak szczególny przypadek problemu plecakowego.Piotr Likus edytował(a) ten post dnia 10.12.09 o godzinie 10:20
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Nie, problem plecakowy to trochę inna brocha.
Ale zgadza się że to problem np zupełny.
Miałem cichą nadzieję ze znajdę gotowy ałgorytm rozwiązujący to przez brute force, ale coś nie widzę.

Dzięki za kod w haskellu, ale szczerze powiem że nie wiem czy bede mógł tego użyć.
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

To ja w Pythonie
Z = [1,2,3,4,5,5,1,2]

W = 8



n = len(Z)





#to poprostu tablica kolejnych liczb zapisanych dwojkowo,

#ale tez definiuje jednoznacznie wszystkie podzbiory



SUBSET_BIN = []

for m in range (0,1+2**(n-1)):

    s = []

    for i in range(1,n+1):

      s.append( m%2 )

      m = m/2

    SUBSET_BIN.append ( s )





#a tu zbior 'prawdziwych' podciagow

#czyli poprostu SUBSET_BIN przemnozony element po elemencie przez Z



SUBSET = []

for s in SUBSET_BIN:

  z = []

  for i in range ( 0,len(s) ):

    t = s[i]*Z[i]

    z.append(t)

  SUBSET.append(z)





#a teraz sprawdzmy, ktory ma dobra sume



WYNIK = []

for s in SUBSET:

  if sum(s) == W: WYNIK.append(s)





#...i drukujemy to co wyszlo



print WYNIK


Starałem się nie używać różnych gotowców, żebyś mógł przetłumaczyć to na jakiś inny język w razie potrzeby. Stąd np. ciąg kolejnych liczb zapisanych binarnie zrobiony jest własnoręcznie, a pewnie łatwiej przetłumaczyć kolejne liczby na ich binarne odpowiedniki jakąś gotową funkcją.

Kod jest totalnie brute-force i pewno można go optymalizować. Ale z reguły im optymalniej, tym mniej czytelnie ;)

Poza tym wynikowe podzbiory są przedstawione w nieco dziwny sposób:
[[1, 0, 3, 4, 0, 0, 0, 0], [1, 2, 0, 0, 5, 0, 0, 0], [0, 0, 3, 0, 5, 0, 0, 0], [1, 2, 0, 0, 0, 5, 0, 0], [0, 0, 3, 0, 0, 5, 0, 0], [1, 2, 0, 4, 0, 0, 1, 0], [0, 0, 3, 4, 0, 0, 1, 0], [0, 2, 0, 0, 5, 0, 1, 0], [0, 2, 0, 0, 0, 5, 1, 0]]

Ma on swoje zalety (widać który konkretnie element był dodany), ale pewnie w większości przypadków należałoby to pozbawić zer i wyeliminować powtórzenia.
Na koniec dodam - u mnie działa ;)Radosław Dominiak edytował(a) ten post dnia 09.01.10 o godzinie 11:26
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Dzięki, temat już ogarnąłem inaczej, ale z ciekawości,

co oznacza zapis
(pierwszy raz widzę pythona na oczy)

for m in range (0,1+2**(n-1)):

oraz

s.append( m%2 )
Link do wypowiedziLink

konto usunięte

Temat: Zadanie dla najlepszych

Henryk Kutypera:
Dzięki, temat już ogarnąłem inaczej, ale z ciekawości,

co oznacza zapis
(pierwszy raz widzę pythona na oczy)

for m in range (0,1+2**(n-1)):

To coś jak
For m = 0 To 2^(n-1)

w VB. Range(a,b) to funkcja zwracająca listę liczb od a do (b-1), więc "for i in range" poprostu przbiegnie po każdym elemencie takiej listy liczb. Przy czym w ogólności elementy listy nie muszą być liczbami.

No i ciekawostka - potęgowanie w Pythonie robimy znaczkiem "**" a nie "^".
s.append( m%2 )

A to poprostu dołączanie do listy s elementu m%2. Operator "%" to dzielenie modulo, więc m%2 to reszta z dzielenia m przez 2.

Swoją drogą Pythona bardzo polecam - jedyny język w którym pisanie naprawdę sprawia przyjemność. Może po tym moim tego nie widać, ale pythonowy kod ogólnie jest bardzo ładny. Ja dawno nie programowałem, więc zapomniałem trochę jak pisać dobry pythonowy kod. No i nie chciałem przesadzać z pythonizmami, żeby kod dało się łatwo przepisać na co innego.

Dodam też, że dla Pythona istnieje ogrom bibliotek. Od jakichś czysto naukowych (dla numeryków, biologów, fizyków) po biblioteki do grafiki czy multimediów. Poza tym język jest dość młody, więc jeszcze nie ma tu takiego bajzlu ja w przypadku C++.

No i Google i NASA używają Pythona :)

Jedyne co może być wadą to to, że ten język chyba bardziej kochają Linuksowcy niż Windowsowcy, więc pewnie pod Linuksem jest łatwiej. Na przykład projektowanie interfejsów graficznych z użyciem Qt czy GTK, albo rysowanie wykresów przez gnuplota jest pod Linuksem skrajnie proste, bo wszystkie kompnenty zwykle już są w systemie, z kolei pod Windows może to być dość pokrętne do zrobienia. Ale może się mylę i Windows jakieś swoje pythonowe rozwiązania też ma.
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

OFERTA PRACY DLA MATEMATYKÓW




Wyślij zaproszenie do
Anuluj