|
Titlul: Greedy Scris de: Maria Mihaela din Octombrie 18, 2015, 21:42:29 Hello loome!!
Am nevoie de ajutor cu o problema cu care imi tot bat capul de cateva ore: :readthis:. Intr-o inchisoare sunt n detinuti, costul mesei fiecaruia fiind c1,c2,...,cn.Pentru a se descurca din S lei sa se mute un nr minim de detinuti intr-o alta inchisoare. Sa se tipareasca numerele de ordine ale detinutilor ce vor ramane in inchisoare. Exemplu: detinuti.in detinuti.out 7 15 1 2 3 5 7 1 3 2 5 2 7 4 Pls heeeelp! Multumesc anticipat! =D> Titlul: Răspuns: Greedy Scris de: Valeriu Motroi din Octombrie 19, 2015, 07:33:55 ce restricții are problema ?
pare mai mult să fie problema rucsacului(adică programare dinamică) Titlul: Răspuns: Greedy Scris de: Alexandru Valeanu din Octombrie 19, 2015, 10:54:26 Dacă am înțeles bine problema, se poate rezolva greedy.
1. Sortezi numerele crescător (păstrând indicii). 2. Cât timp suma numerelor rămase este mai mare decât S, îl elimini pe cel mai mare dintre ele. Complexitate O(N log N). |