Il mio codice sbaglia l’output dei casi 3, 5 e 9 ma non capisco dove sia il problema.
Gradirei un piccolo indizio (magari un input particolare che il mio codice sbaglia) per poter poi capire autonomamente cosa non va bene.
Ecco il codice: https://hastebin.com/oqocibifok.cpp
Grazie della disponibilità.
Riusciresti a spiegare cosa fa il tuo algoritmo?
Controlla se la condizione fra ciascun elemento V[i] (i va da 0 a N-2) e V[j] (j va da i + 1 a N - 1)
NON è verificata. Quando questo accade, significa che almeno 1 dei 2 numeri va eliminato perchè se rimanessero insieme la condizione di validità del subset non sarebbe valida (la condizione è che nel subset risultante S: (S[i] % S[j] == 0 || S[j] % S[i] == 0). Perciò diminuisce la cardinalità massima e decide quale dei due numeri eliminare, contando con quanti numeri del subset può coesistere V[i] e con quanti può coesistere V[j]. A questo punto elimina quello con il numero minore di elementi compatibili e il procedimento ricomincia. Spero sia comprensibile.
Ho trovato un input per il quale sbaglia, infatti con il vettore V[8]={2,14,10,22,34,3,9,27}, invece di dare in output 3,dato dal sottoinsieme {3,9,27}, da 2, il problema si presenta quando confronta 2 e 3: 2 è divisore di 2,14,10,22,34(quindi i_pairs=5), 3 solo di 3,9,27 (quindi i_pairs=3), il programma eliminerà pertanto 3 pur non dovendolo fare, dato che tra 14,10,22,34 nessuno divide un altro, mentre 9 divide 27.
Grazie ora vedo come risolvere 