[c++] rozkroj jednowymiarowy algorytmem zachlannym

Problemy dotyczące programowania.

Moderatorzy: Moderatorzy, Administratorzy

Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

[c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: millena »

Stosowany algorytm: zachlanny, FFD

Gdzies sie zgubilam piszac i jakos nie moge drogi zalapac. Znowu mam zagadnienie optymalizacyjne.
Wycinam preciki.
Mam zadana dlugosc polfabrykanta i i ilosc polfabrykant w magazynie.
Z tego wycinam to, co mam w wektorze zamowienia czyli np 10 pretow dlugosc 300, 20 pretow dlugosc 200 etc.
Mam to zrobic tak, aby odpad byc nie mniejszy niz jakas zadana wielkosc.

Na wyjsciu musze otrzymac wektor wykonanego zamowienia i wektor odpadow.

Kawalek kodu:

Kod: Zaznacz cały

#include <iostream>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main()
{
    

    int dlPolfabrykant;
    const double minCiecie = 0.1;
    const int minRozDetalu = 30;
    cout << "\t\t\t Podaj długość półfabrykantu: " << endl;
    cin >> dlPolfabrykant;
    int iloscPolfabrykant = 100;

    ifstream plikZamowienie("zamowienie.txt");

    vector<int> vecZamowienie;
    //int element, ilosc;

    string lineTemp;
    if (plikZamowienie)
    {
        int element, ilosc;
        while (plikZamowienie >> element >> ilosc)
        {
            for (int i = 0; i < ilosc; i++)
                vecZamowienie.push_back(element);
        }
        plikZamowienie.close();
    }
    cout << endl << endl;
    sort(vecZamowienie.begin(),vecZamowienie.end());
    reverse(vecZamowienie.begin(),vecZamowienie.end());
    for (int i = 0; i < vecZamowienie.size(); i++)
        cout << vecZamowienie[i] << " | ";


    //wycinanie

    vector<int> wykonane;
    vector<int> odpady;

    int dlugoscTemp = dlPolfabrykant;

        while (iloscPolfabrykant != 0)
        {
            while(dlugoscTemp >= minRozDetalu)
            {
                for (int i = 0; i < vecZamowienie.size(); i++)
                {
                    if(vecZamowienie[i] <= dlugoscTemp)
                    {
                        wykonane.push_back(vecZamowienie[i]);
                        dlugoscTemp = dlugoscTemp - vecZamowienie[i];
                    }
                }
            }
            odpady.push_back(dlugoscTemp);
            iloscPolfabrykant--;
        }

   cout << endl << endl << "\t\t WYKONANE: " << endl << endl;

   for (int i = 0; i < wykonane.size(); i++)
        cout << wykonane[i] << " | ";

   cout << endl << endl << "\t\t ODPADY: " << endl << endl;

   for (int i = 0; i < odpady.size(); i++)
        cout << odpady[i] << " | ";

    return 0;
}


Mam zastosowac algorytm zachlanny (np FFD), czyli:
1. Sortuje zamowienia malejaco
2. Biore dlugosc polfabrykanta i sprawdzam czy da sie w niej wyciac najdluzsze zamowienie.
3 Jezeli tak: to dodaje element do wykonanych zamowien, zmiejszam dlugosc fabtrykant = fabrykant - zamowienie;
4. sprawdzam czy kolejne zamowienie miesci sie z fabrykancie
5 jak tak to tne dalej
6, jak nie wrzucam wartosc ktora zostala do wektora odpadow biore nastepny fabrykant

musze pamietac ze minimalna dlugosc odpadu jest zadana.

Ktos mi pomoze??? :) Nie wydaje sie trudne na oko, ale gdzies sie pogubila ;-(
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
mina86
Moderator
Posty: 3343
Rejestracja: 2004-06-14, 21:58
Lokalizacja: Linux 5.x x86_64
Kontakt:

Re: [c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: mina86 »

„ilosc”
Liczbę.

Kod: Zaznacz cały

    sort(vecZamowienie.begin(),vecZamowienie.end());
    reverse(vecZamowienie.begin(),vecZamowienie.end());
To można przez jedno sort zrobić z podanym komparatorem lub w dalszym kodzie zamienić kolejność przechodzenia po wektorze.

A w ogóle, to nie usuwasz elementów z vecZamowienie. Ja to bym tam użył mapy tak w ogóle.
Zastrzegam sobie prawo nieanalizowania postów pisanych niepoprawną polszczyzną.
Post generated automatically by A.I. system code name ‘mina86’ in response to the previous one.
Awatar użytkownika
mina86
Moderator
Posty: 3343
Rejestracja: 2004-06-14, 21:58
Lokalizacja: Linux 5.x x86_64
Kontakt:

Re: [c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: mina86 »

Kod: Zaznacz cały

#include <iostream>
#include <map>

int main() {
	unsigned length, count, l, n;
	std::cin >> length >> count;

	typedef std::map<unsigned, unsigned, std::greater<unsigned> > Items;
	Items items;
	Items::iterator it, end = items.end();

	while (std::cin >> l >> n) {
		items[l] += n;
	}

	while (!items.empty() && count) {
		l = length;
		for (it = items.begin(); it != end; ) {
			while (it->first < l && it->second) {
				l -= it->first;
				--it->second;
				std::cout << it->first << ' ';
			}

			if (!it->second) {
				items.erase(it++);
			} else {
				++it;
			}
		}

		std::cout << "| " << l << '\n';
		--count;
	}

	std::cout << "-- left --\n" << length << ' ' << count << '\n';
	for (it = items.begin(); it != end; ++it) {
		std::cout << it->first << ' ' << it->second << '\n';
	}

	return 0;
}
Zastrzegam sobie prawo nieanalizowania postów pisanych niepoprawną polszczyzną.
Post generated automatically by A.I. system code name ‘mina86’ in response to the previous one.
Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

Re: [c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: millena »

Jak posortować mapę rosnąco???? (muszę coś dopisać do programu i ostro walczę ;P ale tego nie mogę znaleźć) :rotfl:

http://pastebin.com/8ZFQ7V1D

Potrzebuje jako dlPolfabrykant brac kolejne elementy w pliku Magazyn :neutral:
(jeżeli element za mały to ma go zostawiać i spr następny, a jeżeli potnie go tak, że odpad jest mniejsze niż MinDlDetalu to ma go wywalic z Magazynu i przenieść do odpadow)

i nie wiem, gdzie wstawić dokładnie wywalanie z magazynu elementu, bo juz sie nie nadaje - tak aby bral nastepny.

Coś zaczęłam już, ale jak coś nie tak, że mi ktoś poprawić :) ?
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
Awatar użytkownika
mina86
Moderator
Posty: 3343
Rejestracja: 2004-06-14, 21:58
Lokalizacja: Linux 5.x x86_64
Kontakt:

Re: [c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: mina86 »

Wyrzuć std::greater<unsigned> z listy argumentów szablonu i będzie rosnąco.
Zastrzegam sobie prawo nieanalizowania postów pisanych niepoprawną polszczyzną.
Post generated automatically by A.I. system code name ‘mina86’ in response to the previous one.
Awatar użytkownika
millena
Użytkownik
Posty: 124
Rejestracja: 2006-03-20, 14:37
Lokalizacja: /dev/null
Kontakt:

Re: [c++] rozkroj jednowymiarowy algorytmem zachlannym

Post autor: millena »

Kod: Zaznacz cały

#include <iostream>
#include <fstream>
#include <map>

typedef std::map<unsigned, unsigned, std::greater<unsigned> > Zamowienie;
typedef std::map<unsigned, unsigned, std::greater<unsigned> > Magazyn;


static void wczytajZam(Zamowienie &zamowienie, const char *nazwapliku)
{
    std::ifstream plik(nazwapliku);
    unsigned element, ilosc;

    while (plik >> element >> ilosc)
    {
        zamowienie[element] += ilosc;
    }
}

static void wczytajMag(Magazyn &magazyn, const char *nazwapliku)
{
    std::ifstream plik(nazwapliku);
    unsigned element, ilosc;

    while (plik >> element >> ilosc)
    {
        magazyn[element] += ilosc;
    }
}

static bool dlugoscOK(unsigned polfabryknat, unsigned element, unsigned min)
{
    return element + min <= polfabryknat || polfabryknat == element;
}

int main()
{
    unsigned dlPolfabrykant, dlugoscTemp, licznik = 0, minRozDetalu = 30;
    Zamowienie zamowienie;
    Zamowienie::iterator it, end = zamowienie.end();
    Magazyn magazyn;
    Magazyn::iterator jt, koniec = magazyn.end();

    std::cout <<
    "\t\t ..:: APLIKACJA DO ROZKROJU JEDNOWYMIAROWEGO SUROWCA  ::.. \n"
    "\t\t :: WOJCIESZKO Tomasz, KOSINSKA Monika ::\n";

    wczytajZam(zamowienie, "zamowienie.txt");
    wczytajMag(magazyn, "magazyn.txt");
    std::cout << std:: endl;

    for (jt = magazyn.begin(); jt != koniec; jt++) //jest petla, ale sprawdza tylko elem z pierwszej  kolumny, nie bierze pod uwage drugiej
    //i nie wiem, jak usuwac elementy, ktore sie juz nie nadaja do uzytku, czyli sa mniejsze rowne MinDetalowi :/
    {

        dlPolfabrykant = jt -> first;

        std::cout << "\npolfabrykant: " << dlPolfabrykant << std::endl;

        std::cout << std:: endl;

        std::cout << "\t\tZAMOWIENIE: \n\n";

        for (it = zamowienie.begin(); it != end; )
        {
            std::cout << "\t" << it -> first << ' ' << it -> second;

            if (dlugoscOK(dlPolfabrykant, it -> first, minRozDetalu))
            {
                ++it;
            }

            else
            {
                std::cout << "\t : element za duzy, odrzucam";
                zamowienie.erase(it++);
            }

            std::cout << '\n';
        }

        std::cout << "\tWYCINANIE ZAMOWENIA: \n\n";
        while (!zamowienie.empty())
        {
            dlugoscTemp = dlPolfabrykant;
            for (it = zamowienie.begin(); it != end; )
            {
                while (dlugoscOK(dlugoscTemp, it -> first, minRozDetalu))
                {
                    dlugoscTemp -= it -> first;
                    std::cout << it -> first << ' ';
                    if (!--it -> second)
                    {
                        break;
                    }
                }


                if (!it -> second)
                {
                    zamowienie.erase(it++);
                }
                else
                {
                    ++it;
                }
            }
            std::cout << " | odpadzik: " << dlugoscTemp << '\n';
            magazyn.erase(jt->first);
            magazyn.erase(jt->second);
            ++licznik;
        }
    }

    std::cout << "\t\t\tWykorzystano  " << licznik << " polfabryknat(y/ow)\n";

    return 0;
}
Wycina mi tylko z pierwszego elementu z Magazynu :/
[color=green]dd if=/home/millena of=/dev/null [/color]-> [color=olive]od kiedy kieruje backupy do /dev/null idą o wiele szybciej [/color] [img]http://mandrivauser.ovh.org/.image/fftoie.gif[/img]
ODPOWIEDZ