Quindi io e il mio amico abbiamo trovato una domanda di algoritmo piuttosto interessante (forse?) ma, ironia della sorte, stiamo facendo fatica a risolverlo. La domanda è:
C'è una vendita di pietre preziose in corso in una città dei ricchi. Ogni pietra in vendita ha una o più varianti di esso. Ad esempio, un diamante può essere rotondo, ovale, cuscino, ecc. Ogni variante deve essere contata come una pietra separata.
Le pietre sono posizionate in questo modo (esempio):
Diamond Ruby Emerald Sapphire
round red colorless
oval green
cushion
Questo tipo di posizionamento impedisce la formazione di un array 2D perfetto, poiché il numero di tipi di ciascuna pietra può variare.
Ora i clienti ricchi vengono a comprare le pietre e ogni cliente ha un set di pietre che gli piace. Un cliente sarà soddisfatto se sarà in grado di acquistare almeno una delle pietre che preferisce.
Dato il numero di clienti, il numero di pietre e le varianti associate, scopri se è possibile soddisfare tutti i clienti .
Bonus: se possibile, trova le pietre acquistate da ciascun cliente.
Nota: le preferenze dei clienti non possono essere vuote, ad esempio, a ogni cliente piace almeno una pietra.
Cosa ho provato
(per scoprire se è possibile soddisfare tutti i clienti)
Backtracking:
Abbiamo un elenco di preferenze per ogni cliente. Quindi, basta assegnare la prima pietra possibile al cliente (dalla sua lista) e passare al prossimo cliente. Continua a farlo per tutti i clienti.
Se, per un cliente, non è possibile assegnare una pietra, andare al cliente precedente e cambiare la pietra assegnata.
Ripeti fino a quando almeno una pietra viene assegnata per ogni cliente.
Se torni al primo cliente e se non assegni alcuna pietra può portare alla soluzione, stampa "Impossibile".
Ho delle seguenti preoccupazioni su questo algoritmo (supponendo che sia corretto):
- È difficile da implementare. Ho incontrato troppe variabili temporanee mentre provavo a implementarlo. (L'ho lasciato a metà).
- Sembra una specie di forza bruta, perché in realtà sto provando ogni possibile combinazione.
Questo algoritmo è corretto? Può essere migliorato? Esiste un'alternativa facile da implementare?