Greedy

[•mareare14]

Hello loome!!
Am nevoie de ajutor cu o problema cu care imi tot bat capul de cateva ore: . 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!

[•Djok]

ce restricții are problema ?
pare mai mult să fie problema rucsacului(adică programare dinamică)

[•AlexandruValeanu]

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).