Greedy de acoperire: dacă putem forma orice valoare din [0, reach] și adăugăm o cutie de mărime s <= reach+1, acoperim [0, reach+s]. Alegem mereu cea mai mare cutie utilizabilă și adăugăm copii în loturi ca să nu depășim timpul.
Vezi enunțul oficialÎncearcă întâi singur! Indiciile elimină din satisfacția rezolvării.
Gândește-te la ce cantități poți deja livra. La început nu poți livra nimic, dar pe măsură ce pregătești cutii intervalul de cantități acoperite crește. Ideea e simplă: ținem un singur număr, — cea mai mare cantitate până la care putem livra orice valoare folosind cutiile alese. Vrem cu cât mai puține cutii.
Conectează-te ca să marchezi problemele rezolvate.