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