Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- #include <algorithm>
- //---
- const char DUOM[]= "duom.txt";
- /*
- 12 užduotis.
- Duota N daiktų, kurių tūriai v1, v2, v3, .., vn.
- Į kokį mažiausią skaičių tūrio M dėžučių galima sudėti šiuos daiktus?
- SKAITYMO FAILAS TURI ATRODYT TAIP:
- m
- v1 v2 v3....
- kai m- dezutes dydis
- v1, v2... - daiktu turiai
- */
- //---
- int V[255];
- int n=0;
- int m;
- int M[255];
- int minDez = 0;
- int minDezExp=0;
- int maxDez;
- bool klaida = false;
- //--
- void skaityk (const char DUOM[], int V[], int &n, int &m, bool &klaida, int &minDezExp);
- void rikiuoti (int V[], int n);
- void idetiDidziausius(int V[], int M[], int m, int &n);
- void isimtiElem(int V[], int M[], int mi, int vi);
- void istrintiElementa (int V[], int &n);
- int dabarMinDez (int M[], int maxDez);
- void rekursija (int V[], int M[], int n, int m, int mi, int vi, int maxDez, int &tempMin, int minDezExp);
- //--
- using namespace std;
- int main()
- {
- skaityk (DUOM, V, n, m, klaida, minDezExp);
- if(klaida) return 0;
- else
- {
- rikiuoti (V, n);
- if (n==1)
- {
- minDez++;
- n=0;
- }
- else
- {
- maxDez = n;
- idetiDidziausius(V, M, m, n);
- if (n!=0)
- {
- int tempMin= maxDez;
- rekursija(V, M, n, m, 0, 0, maxDez, tempMin, minDezExp);
- minDez=tempMin;
- }
- }
- cout << endl << endl;
- cout << "Maziausiai reikes "<< minDez << " dezuciu sutalpinti visus objektus"<< endl;
- return 0;
- }
- }
- void skaityk (const char DUOM[], int V[], int &n, int &m, bool &klaida, int &minDezExp)
- {
- ifstream fd (DUOM);
- bool neig = false;
- bool perDaug = false;
- fd >> m;
- int i = 0;
- while (!fd.eof())
- {
- fd >> V[i];
- if (V[i]< 0)
- neig = true;
- if (V[i]> m)
- perDaug=true;
- minDezExp = minDezExp + V[i];
- i++;
- n++;
- }
- fd.close ();
- if (n == 0)
- {
- cout << "Failo nepavyko nuskaityti arba jis yra tuscias"<< endl;
- klaida= true;
- }
- else if (perDaug)
- {
- cout << "Jus pasirinkote per didelius objektus, kurie netelpa i dezute. Nereikia taip daryti"<< endl;
- cout << "Darbas baigtas. Noredami testi, pakeiskite duomenis"<< endl;
- klaida = true;
- }
- else if (neig)
- {
- cout << "Jus ivedete neigiamo turio objektus. Nereikia taip daryti" << endl;
- cout << "Darbas baigtas. Noredami testi, pakeiskite duomenis"<< endl;
- klaida = true;
- }
- else
- {
- cout << "Turime "<< n << " skirtingu dydziu objektu, kuriu turiai: " ;
- for (int i = 0; i < n; i++)
- cout << V[i]<< " ";
- cout << endl;
- cout << "Juos turime optimaliai sudeti i " << m << " dydzio talpas" << endl<<endl;
- if (minDezExp%m == 0)
- minDezExp = minDezExp/m;
- else
- minDezExp = minDezExp/m +1;
- cout << "Jei tai butu vanduo sutalpintumem i " << minDezExp << " dezutes" << endl;
- }
- }
- void rikiuoti (int V[], int n)
- {
- for (int j = 0; j < n; j++)
- {
- for (int i= 0; i < n-1; i++)
- {
- if (V[i]>V[i+1])
- swap (V[i],V[i+1]);
- }
- }
- }
- //IDEDAM TUOSS, KURIE YRA DIDESNI NEI PUSE M
- void idetiDidziausius(int V[], int M[], int m, int &n)
- {
- int vi = n-1;
- int mi = 0;
- while ((vi >= 0)&& (V[vi] > m/2))
- {
- M[mi]= V[vi];
- istrintiElementa(V, n);
- mi++;
- vi--;
- }
- }
- void rekursija (int V[], int M[], int n, int m, int mi, int vi, int maxDez, int &tempMin, int minDezExp)
- {
- if (vi==n-1) //JEI PRIEJOM PASKUTINI NARI
- {
- int i =0;
- mi=0;
- for (mi; mi<maxDez;mi++)
- {
- if ((m -M[mi]) >= V[vi])//JEI TELPA,
- {
- M[mi] = M[mi]+ V[vi];//IDEDAM IR
- if (tempMin > dabarMinDez(M,maxDez)) //TIKRINAM, AR OPTIMALIAU
- tempMin=dabarMinDez(M,maxDez);
- isimtiElem(V, M, mi, vi); //ISIMAM ELEM IR TIKRINAM TOLIAU
- }
- }
- return;//GRIZTAM KEISTI KITAS REIKSMES
- }
- //CIKLAS, KAI DELIOJAM VISAS DEZUTES(ISSKYRUS PASKUTINE)
- for (mi; mi < maxDez; mi++)//CIKLAS TIKRINTI TINKAMAS DEZUTES
- {
- if (mi == maxDez-1) //JEI PASKUTINE DEZUTE..
- {
- if ((m -M[mi]) < V[vi])//IR JOJE NETELPA
- return; //RETURNINAM
- }
- if ((m -M[mi]) >= V[vi])//JEI TELPA..
- {
- M[mi] = M[mi]+ V[vi];//IDEDAM
- if (tempMin < dabarMinDez(M,maxDez)) //JEI IR BE PASKUTINIO ELEMENTO, TAI NERA OPTIMALIAU
- return;//ISKART RETURNINAM
- rekursija(V, M, n, m, 0, vi+1,maxDez,tempMin,minDezExp);//IR IMAM KITA DAIKTA
- if (tempMin==minDezExp)
- return;
- //return;
- isimtiElem(V, M, mi, vi);//KAI GRIZTAM, ISTRINAM ELEMENTA
- }//IR DEDAM I KITA DEZUTE
- }
- }
- void isimtiElem(int V[], int M[], int mi, int vi)
- {
- M[mi] = M[mi]- V[vi];
- }
- int dabarMinDez (int M[], int maxDez)
- {
- int x= 0;
- for (int i = 0; i < maxDez; i++)
- {
- if (M[i] != 0) x ++;
- }
- return x;
- }
- void istrintiElementa (int V[], int &n )
- {
- n--;
- V[n] = 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement