Mi sembra che, per il problema dato, avida sia sempre la migliore.
Tuttavia, in generale, passerei da sinistra a destra attraverso l'elenco, mantenendo un elenco completo di tutte le possibilità; se ci sono due o più possibilità che ti atterrerebbero nello stesso punto, poti ogni possibilità che non è la più efficiente (a seconda della domanda, potresti anche potare tutte tranne una delle soluzioni identicamente efficienti). Elimina regolarmente ogni soluzione che è un vicolo cieco.
Quindi, per il tuo esempio (elencherò ogni possibilità tra parentesi):
- Passa al primo elemento dell'array - 1. Devi iniziare da qui, quindi rendi questo il tuo elenco di possibilità: (1)
- Passa all'elemento successivo dell'array - 3
- Per ogni elemento nel tuo elenco di possibilità, copialo, aggiungi l'elemento nell'array e aggiungilo all'elenco di possibilità: (1), (1,3)
- Elimina qualsiasi possibilità non valida o possibilità che non possono mai essere valide (nessuna ancora)
- Per qualsiasi coppia di possibilità che finiscono nello stesso posto, elimina tutto tranne il più efficiente (ancora nessuno)
- Passa alla voce successiva del tuo elenco - 5
- Per ogni elemento del tuo elenco di possibilità, copialo, aggiungi l'elemento nell'array e aggiungilo all'elenco di possibilità: (1), (1,3), (1,5), (1 , 3,5)
- Elimina qualsiasi possibilità non valida o possibilità che non possono mai essere valide (nessuna ancora)
- Per ogni coppia di possibilità che finiscono nello stesso posto, spoglia tutto tranne il più efficiente. (1,5) e (1,3,5) entrambi terminano con 5 e (1,5) è più efficiente, quindi elimina (1,3,5).
- Passa al prossimo elemento del tuo elenco - 10
- Per ogni elemento del tuo elenco di possibilità, copialo, aggiungi l'elemento nell'array e aggiungilo all'elenco di possibilità: (1), (1,3), (1,5), (1 , 10), (1,3,10), (1,5,10)
- Elimina qualsiasi possibilità non valida o possibilità che non possono mai essere valide. (1,10) e (1,3,10) non sono validi, e (1) e (1,3) non saranno mai validi (ipoteticamente, (1,5) potrebbe essere valido, se questo 10 è seguito da un altro 10 ). Questo lascia (1,5), (1,5,10)
- Per qualsiasi coppia di possibilità che finiscono nello stesso posto, elimina tutte tranne le più efficienti (nessuna trovata).
- Passa alla voce successiva del tuo elenco - 15
- Per ogni elemento del tuo elenco di possibilità, copialo, aggiungi l'elemento nell'array e aggiungilo all'elenco delle possibilità: (1,5), (1,5,10), (1,5 , 15), (1,5,10,15),
- Elimina qualsiasi possibilità non valida o possibilità che non possono mai essere valide. (1,5,15) non è valido e (1,5) non sarà mai valido. Questo lascia (1,5,10), (1,5,10,15)
- Per qualsiasi coppia di possibilità che finiscono nello stesso posto, elimina tutte tranne le più efficienti (nessuna trovata).
- Lavare, risciacquare, ripetere.
Quindi il metodo generale è:
- rende le cose un po 'più complicate
- rimuovi quelli che puoi rimuovere
