Angajari

O firmă dorește să facă noi angajări. Firma are la dispoziție o suma s și dorește să angajeze câte o persoană, pe un anumit număr de luni, astfel încât perioada pe care își angajează salariații să fie cât mai mare. S-au primit cererile a n persoane împreună cu pretențiile lor salariale pentru un an. Astfel pentru a lucra j luni la firmă (1≤j≤12), persoana i cere a[i,j] euro.
Cerință
Cunoscându-se numarul n de cereri, suma s de care dispune firma și matricea a cu pretențiile salariale ale celor n persoane se cere să se determine numarul maxim de luni pe care firma poate angaja noi salariați, costul total al angajărilor și numărul de luni pe care va fi angajată fiecare persoană.
Date de intrare: fișierul work.in cu urmatoarea structură:
Linia 1: n s
Linia 2: a[1,1] a[1,2] … a[1,12]
Linia 3: a[2,1] a[2,2] … a[2,12]
………………………………
Linia n+1:a[n,1] a[n,2] … a[n,12]
Astfel, pe prima linie sunt numarul n de cereri și suma s de care dispune firma, separate prin spațiu, iar pe fiecare din următoatele n linii sunt pretențiile salariale ale fiecărei persoane pe cele 12 luni.
Date de ieșire: fișierul work.out cu următoarea structură:
Linia 1:     x p
Linia 2:     l1
Linia 3:     l2
………….
Linia n+1: ln
unde, x reprezinta numărul maxim de luni pe care angajează firma salariați, p reprezintă costul total al angajărilor, iar li reprezintă numărul de luni pe care este angajată persoana i (li poate fi 0 dacă persoana nu va fi angajată).
Restricții și precizări:
1 ≤ n ≤40
1 ≤ s ≤ 32000
1≤ a[i,j] ≤ 10000

Orice persoana poate fi angajată o singură data și pe o perioadă de cel mult un an (12 luni).
Oricare ar fi i, x1, x2, daca x1<x2 atunci a[i,x1]<a[i,x2] adică pentru mai multe luni de munca persoana va cere mai multi bani.
În cazul în care există mai multe soluții se va afișa cea cu costul total al angajărilor minim.
Ce metoda backtracking sau metoda greedy se poate rezolva?

Tricer, on 11th February 2012, 15:03, said:

Bănuind că tu de fapt întrebi: ”Cu ce metoda backtracking sau metoda greedy se poate rezolva?” eu te întreb: ”Ce metodă backtracking sau metodă greedy știi?”.

amandoua am inceput un pic la rezolvarea problemei

Tricer, on 11th February 2012, 16:13, said:

Prietene, eu am învățat la liceu că backtracking folosești când trebuie să afli toate soluțiile iar greedy când ai nevoie de soluția cea mai bună ( mie mi s-a spus la liceu că greedy e de fapt un fel de backtracking ”spart” ). Deci trebuie folosit greedy.
Citește și asta și poate te ajută.

poti sa ma ajuti cu problema?

Tricer, on 11th February 2012, 17:22, said:

Dai cod ce ai făcut și spui unde nu înțelegi iar cei de aici te ajută. Oricum, cred că ar trebui să vorbești cu un moderator ca să-ți mute topicul aici.

P.S.: Dacă cumva prin a te ajuta cu problema înseamnă a-ți face problema ( sunt sigur că nu te refereai la asta ) atunci nu te pot ajuta.
P.P.S.:Uite ce am înțeles eu citind link-ul ce ți l-am dat. Spunea acolo că tehnica greedy este o tehnică ”lacomă” în sensul că se alege cel mai optim pas pe moment. Deci eu cred că ar trebui să ordonezi angajații după suma minimă cerută pe un număr de luni cât mai mare și în aceată ordine să adaugi câți angajați permite suma respectivă.

Adica se cere sa se maximizeze numarul cumulat de luni de la fiecare persoana? Adica dorel lucreaza 5 luni iar vasile 7 luni in total se considera 12 luni?

trident, on 11th February 2012, 18:19, said:

Tu trebuie să sortezi muncitorii ( cel puțin așa cred eu ) după numărul maxim de luni ce ar lucra un angajat pe cât mai puțini bani. Exemplu dacă dorel lucrează 7 luni cu 10000 lei atunci îl vei prefera pe acesta în locul lui vasile care ar lucra 5 luni cu 10000 lei.

Saurian, on 11th February 2012, 16:49, said:

"Prietene", Greedy te duce doar in optime locale.. Daca la final s-a nimerit ca unul din ele sa fie si cel global, super. Daca nu.. nu.

msmihai, on 11th February 2012, 19:01, said:

Eu m-am referit strict la cazul lui când era sau backtracking sau greedy. Ok, nu m-am exprimat foarte bine în a explica asta.

Saurian, on 11th February 2012, 18:35, said:

defapt e cam asa : trebuie sa alegi muncitorii in asa fel in cat sa obtii cat mai multe luni in care sa fie lucratori angajati iar salariile pe lunile angajate sa nu depaseasca s citit din fisier (cum ar veni 'bugetul')

xs1lv1ux, on 11th February 2012, 20:00, said:

problema se rezolva cu backtracking

Editat de xs1lv1ux, 11 februarie 2012 - 20:05.

xs1lv1ux, on 11th February 2012, 20:00, said:

eu as dori doar niste instructiune pe care o sa le dezvolt eu
un prim pas ar fi
#include<iostream>
using namespace std;
main ()
{
int a[100],n,m,s;
cout<<"numarul de muncitor";cin>>n;
for(int i=1;i<=n;i++)
cout<<"suma ";cin>>s;
for(int j=1;j<=12;j++)suma va creste pe fiecare luna fiecare angajat nu poate sta mai mult de un an
{cin>>a[i,j];se citest sumele fiecarui angajat pe fiecare luna
for(i=1;i<=n;i++)
for(j=1;j<=12;j++)
metoda de sortare care imi place sa o folosesc este asta
{ int aux;

for(int i=1;i<=n-1;i++)

                for(int j=i+1;j<=n;j++)

                                if(a[i]>a[j])

                                {aux=a[i];a[i]=a[j];a[j]=aux;}

}
dar nu stiu cum sa o modific,si am niste date de testare
Cerință
Cunoscându-se numarul n de cereri, suma s de care dispune firma și matricea a cu pretențiile salariale ale celor n persoane se cere să se determine numarul maxim de luni pe care firma poate angaja noi salariați, costul total al angajărilor și numărul de luni pe care va fi angajată fiecare persoană.
Date de intrare: fișierul work.in cu urmatoarea structură:
Linia 1: n s
Linia 2: a[1,1] a[1,2] … a[1,12]
Linia 3: a[2,1] a[2,2] … a[2,12]
………………………………
Linia n+1:a[n,1] a[n,2] … a[n,12]
Astfel, pe prima linie sunt numarul n de cereri și suma s de care dispune firma, separate prin spațiu, iar pe fiecare din următoatele n linii sunt pretențiile salariale ale fiecărei persoane pe cele 12 luni.
Date de ieșire: fișierul work.out cu următoarea structură:
Linia 1:     x p
Linia 2:     l1
Linia 3:     l2
………….
Linia n+1: ln
unde, x reprezinta numărul maxim de luni pe care angajează firma salariați, p reprezintă costul total al angajărilor, iar li reprezintă numărul de luni pe care este angajată persoana i (li poate fi 0 dacă persoana nu va fi angajată).
Restricții și precizări:
1 ≤ n ≤40
1 ≤ s ≤ 32000
1≤ a[i,j] ≤ 10000

Orice persoana poate fi angajată o singură data și pe o perioadă de cel mult un an (12 luni).
Oricare ar fi i, x1, x2, daca x1<x2 atunci a[i,x1]<a[i,x2] adică pentru mai multe luni de munca persoana va cere mai multi bani.
În cazul în care există mai multe soluții se va afișa cea cu costul total al angajărilor minim.

Quote

se poate pana luni sa rezolv?

Tricer, on 11th February 2012, 20:10, said:

pey tu nu ai nici o trb cu metoda de sortare...

dupa ce ai pus in matrice ideea mea ar fi urmatoarea : parcurge matricea pe coloana de la sfarsit adica j=12 si vezi care dintre angajati are cerintele minime .Apoi treci la urmatoarea coloana adica j=11 si gasesti iar angajatul cu cerinte minime .Dupa ce verifici daca (salariul angajatului cu cerinte minime dp coloana 11 + salariul anterior minim) <s treci la urmatoarea coloana si tot asa pana ajungi la coloana 1...ceva de genu ar trb sa faci.

practic tu trb sa adaptezi ce am spus eu mai sus pe o metoda de backtracking cu care sa faci toate incercarile...

Cu backtracking e imposibil de rezolvat pentru datele de intrare ( intr-un timp rezonabil ). 2^40 = 1 099 511 627 776.

problema se rezolva cu greedy dar se poate sa ma ajutati cu o continuare a problemei?

trident, on 11th February 2012, 21:44, said:

pey nu trb sa ajungi pana la finalul solutiei ca sa iti dai seama daca nu e buna..

Editat de xs1lv1ux, 11 februarie 2012 - 21:54.

http://forum.softped...howtopic=819687