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