Challenge #2

[Patrunjel]

Castigatorul challenge-ului precedent a fost cmiN .Felicitari

De data asta am ceva mai usor, poate asa voi avea mai mult de un participant Clasica problema a rucsacului ( *Disclaimer* Cine cauta pe net rezolvarea problemei suge pula la cai morti *Gada Disclaimeru* ).

Aveti un numar de n obiecte.Pentru fiecare stiti greutatea (kg) si pretul pe care il luati pe obiect, daca il duceti la amanet.Tinand cont ca aveti o Dacia 1310 care duce maxim X kilograme (X citit de la tastatura).Scrieti un program prin care sa stabiliti pe care dintre cele n obiecte le bagati in Dacie, pentru a lua cat mai multi bani (Faceti un singur drum, si nu puteti taia obiectele, au valoare sentimentala)

Si, inca odata, felicitari cmiN

[l3asketballplayer]

baga si tu ceva mai greu

[50cent]

O problema de greedy.

[cmiN]

Nu e greedy fiindca nu poti taia obiectele (valoare sentimentala) e dinamica si am rezolvat-o acum ceva vreme (plus inca cateva care semanau).

E cazul 1-0 (un singur obiect) C++ | #include <cstdio> typedef unsigned int ui_t; c - CmiN

Mai e cazul cand pot fi folosite o infinitate de obiecte si atunci e de ajuns un vector pentru cost nu o matrice.

[Patrunjel]

@cmiN

merge si cu greedy, bagi tot intr-un vector, il sortezi in functie de raportul greutate/castig si apoi afisezi elemente pana greutatea iti ajunge mai mica decat greutatea urmatorului element.Defapt e greedy euristic, ca daca mai ai loc, de ex, pentru 2 kile, si urmatorul element are raport 3/4 da are 5 chile, si unu de pe la urma are, sa zicem, 1/6 raportul eficientei, da are 1 kil, nu ti-l ia pe ala de un chil, doar se opreste, si la suma primita in total nu se aduna si suma pentru ala de un kil.Si iara am scris ca disperatu....

Abea daca ai putea taia obiectele ai avea greedy ne-euristic, care va da rezultatul corect, fara cazuri de-astea de cacat unde face fite

@50cent Daca e de greedy, de ce nu incerci s-o faci si sa te convingi ca nu e, sau sa ne convingi pe noi ca e

PS: Pula, n-avem tag-uri pentru spoiler vreunu care stie cu ce se mananca treaba asta, aveti idee cum sa facem cumva sa ascundem commenturile legate de rezolvare?Adica sa nu dea cineva peste rezolvare fara sa vrea, poate ar fi vrut omu sa vada daca poate singur (asta presupunand ca s-ar dovedi cineva interesat de challenge-uri )

Edited February 28, 2011 by Patrunjel