Complexitate

[•fulgerulnegru]

Cine stie complexitatea de la problema cunoscuta in folclorur de informatica drept impartirea cadourilor?

[•klamathix]

Care e enuntul?

[•visanr]

Iti zic eu: ai n cadouri si le stii preturile. Trebuie sa imparti cat mai echitabil cadourile astfel incat sumele sa fie cat mai apropiate

[•scipianus]

Iti zic eu: ai n cadouri si le stii preturile. Trebuie sa imparti cat mai echitabil cadourile astfel incat sumele sa fie cat mai apropiate

Adica sa le impart in doua multimi astfel incat diferenta sa fie minima? http://infoarena.ro/problema/jocul

[•visanr]

Iti zic eu: ai n cadouri si le stii preturile. Trebuie sa imparti cat mai echitabil cadourile astfel incat sumele sa fie cat mai apropiate

Adica sa le impart in doua multimi astfel incat diferenta sa fie minima? http://infoarena.ro/problema/jocul

Da

[•dushmi]

O (N * S), unde S este suma preturilor cadourilor, iar N este numarul de cadouri.

[•fulgerulnegru]

Multumesc