Allineati sul bordo di un lungo sentiero si trovano dei recipienti cilindrici, aventi tutti la medesima altezza ma diametro diverso.
Camminando lungo il sentiero è possibile raccogliere alcuni di questi recipienti, col vincolo che è possibile raccoglierne uno solo se o è il primo raccolto o ha un diametro minore dell’ultimo raccolto in precedenza; i recipienti devono infatti essere via via posti uno nell’altro, quindi la sequenza delle misure dei diametri dei recipienti via via raccolti deve risultare decrescente.Se la lista dei diametri dei recipienti disposti lungo il sentiero è la seguente:
[5, 4, 1, 5, 9, 8, 6, 2, 5, 3, 2, 4, 1]alcune possibilità di raccolta consentite dal vincolo imposto sono descritte dalle seguenti liste:
- [5, 4, 1]
- [5, 4, 3, 2, 1]
- [9, 8, 6, 5, 3, 2, 1]
In questo esempio, la soluzione 3) è quella che consente di raccogliere il massimo numero di recipienti.
Data la seguente distribuzione dei diametri dei recipienti disposti lungo il sentiero:
[2, 17, 16, 16, 11, 8, 20, 8, 3, 5, 19, 19, 6, 8, 8, 17, 9, 20, 3, 5, 19, 19, 16, 19]trovare il massimo numero N di recipienti che si possono raccogliere, rispettando il suddetto vincolo che la sequenza dei relativi diametri deve risultare decrescente.