✔ rucksackproblem

# include<stdio.h>
# include<conio.h>

void knapsack(int n, float weight[], float profit[], float capacity)
{
 float x[20], tp= 0;
 int i, j, u;
 u=capacity;

 for (i=0;i<n;i++)
     x[i]=0.0;

 for (i=0;i<n;i++)
 {
 if(weight[i]>u)
      break;
 else
     {
     x[i]=1.0;
     tp= tp+profit[i];
     u=u-weight[i];
     }
 }

 if(i<n)
       x[i]=u/weight[i];

 tp= tp + (x[i]*profit[i]);

 printf("n The result vector is:- ");
 for(i=0;i<n;i++)
        printf("%ft",x[i]);

 printf("m Maximum profit is:- %f", tp);

}

void main()
{
 float weight[20], profit[20], capacity;
 int n, i ,j;
 float ratio[20], temp;
 clrscr();

 printf ("n Enter the no. of objects:- ");
 scanf ("%d", &num);

 printf ("n Enter the wts and profits of each object:- ");
 for (i=0; i<n; i++)
 {
 scanf("%f %f", &weight[i], &profit[i]);
 }

 printf ("n enter the capacityacity of knapsack:- ");
 scanf ("%f", &capacity);

 for (i=0; i<n; i++)
 {
 ratio[i]=profit[i]/weight[i];
 }

 for(i=0; i<n; i++)
 {
    for(j=i+1;j< n; j++)
    {
      if(ratio[i]<ratio[j])
      {
      temp= ratio[j];
      ratio[j]= ratio[i];
      ratio[i]= temp;

     temp= weight[j];
     weight[j]= weight[i];
     weight[i]= temp;

     temp= profit[j];
     profit[j]= profit[i];
     profit[i]= temp;
     }
   }
 }

 knapsack(n, weight, profit, capacity);
 getch();
}

//Author: Neko
//Ziel: Tutorials.de

//Vorgabe sind eine liste von Gepäckstücken mit folgenden werten:
//ID | Gewicht | Wert in €
//und eine liste von koffern mit folgenden werten:
//ID [als char] | Gesamtgewicht | Eigengewicht

//Ziel ist es alle Gepäckstücke in den Koffern zu verstauen so dass weder das Gesamtgewicht des Koffers überschritten wird noch der Gesamtwert des Koffers nicht über 200€ liegt

//Die Konstante mit den 200€ habe ich hier im Beispiel früh definiert und sie ist änderbar im Code bei bedarf
//Die liste mit den Gepäckstücken und Koffern wird bei jeden Aufruf neu eingelesen

//Für die ausgabe des ergebnisses auf der Konsole
#include <iostream>

//Für das einlesen der gepäck und kofferlisten
#include <fstream>

//Für die Listen
#include <list>

//zum dateien zeilenweise auslesen
#include <string>

//Maximaer Wert in einem Koffer
#define MAXVALUE 200.00f

using namespace std;

//Gepäckstück
struct Package
{
    //Nummer
    int id;

    //gewicht
    float weight;

    //Wert in €
    //Nutze eine Float-variable um auch cent beträge zu zu lassen
    float value;
};

//Koffer
struct Box
{
    //Koffer"name"
    char id;

    //maximalgewicht
    float max;

    //eigengewicht
    float weight;

    //Beinhaltende Gepäckstücke
    list<Package> packages;

    //Teste ob der Koffer so überfüllt wäre mit diesem Gepäckstück
    bool test(Package add)
    {
        //Testwerte, wenn überschritten, direkter abbruch mit negativ, sonst positiv
        float t_value = 0.0f;
        float t_weight = weight;
        //Durchlaufe jedes Gepäckstück im Koffer
        for (list<Package>::iterator it = packages.begin(); it != packages.end(); ++it)
        {
            //Füge die werte den gesamtwerten hinzu
            t_value += (*it).value;
            t_weight += (*it).weight;
            //teste ob der wert überschritten wurde
            if (t_value > MAXVALUE || t_weight > max)
            {//zu schwer/zu teuer
                return false;
            }
        }
        t_value += add.value;
        t_weight += add.weight;
        //teste ob der wert überschritten wurde
        if (t_value > MAXVALUE || t_weight > max)
        {//zu schwer/zu teuer
            return false;
        }

        //Keine überschreitung gefunden, also gut soweit
        return true;
    }

    //Funktionen für das gesamtgewicht und den gesamtwert
    float allweight()
    {
        float t_weight = weight;
        //Durchlaufe jedes Gepäckstück im Koffer
        for (list<Package>::iterator it = packages.begin(); it != packages.end(); ++it)
        {
            //Füge die werte den gesamtwerten hinzu
            t_weight += (*it).weight;
        }
        return t_weight;
    }
    float allvalue()
    {
        float t_value = 0.00f;
        //Durchlaufe jedes Gepäckstück im Koffer
        for (list<Package>::iterator it = packages.begin(); it != packages.end(); ++it)
        {
            //Füge die werte den gesamtwerten hinzu
            t_value += (*it).value;
        }
        return t_value;
    }
};

//Liest die Gepäckliste ein
list<Package> readPackages()
{
    cout << "Gepäck einlesen:" << endl;
    //Rückgabewert
    list<Package> ret;
 
    //Dateihandler und direkt öffnen
    fstream f;
    f.open("Packages.list.txt", ios::in);
    //Fehler?
    if (!f)
    {
        cout << "Packages.list.txt konnte nicht geöffnet werden" << endl;
        getchar();
        exit(NULL);
    }
    //und einmal bis zum ende durchlesen
    while (!f.eof())
    {
        //Temporär, um eine zeile zu bearbeiten
        string line;
        Package pkg;
        //eine zeile aus der datei lesen
        getline(f,line);

        //id einlesen
        cout << "id:" << (pkg.id = atoi(line.c_str()));


        //anfang der line sicher abschneiden
        if (line.find(' ') == string::npos)
        {//ups, da fehlt ein Leerzeichen, vergiss diese line
            cout << endl;
            continue;//und mach mit der nächsten weiter
        }
        line = line.substr(line.find_first_of(' '));
        //auf weitere leerzeichen prüfen
        while (line.front() == ' ')
        {
            line = line.substr(1);
        }

        //Gewicht einlesen
        cout << " weight:" << (pkg.weight = atof(line.c_str()));

        //anfang der line sicher abschneiden
        if (line.find(' ') == string::npos)
        {//ups, da fehlt ein Leerzeichen, vergiss diese line
            cout << endl;
            continue;//und mach mit der nächsten weiter
        }
        line = line.substr(line.find_first_of(' '));
        //auf weitere leerzeichen prüfen
        while (line.front() == ' ')
        {
            line = line.substr(1);
        }

        //Wert einlesen
        cout << " value:" << (pkg.value = atof(line.c_str()));
        cout << " bestätigt" << endl;

        //alle werte eingelesen: in liste einfügen
        ret.push_back(pkg);

    }


    //Schön wieder schließen
    f.close();

    return ret;
}

//liest die Kofferliste ein
list<Box> readBoxes()
{
    cout << "Koffer einlesen:" << endl;
    //Rückgabewert
    list<Box> ret;
    //Dateihandler und direkt öffnen
    fstream f;
    f.open("Boxes.list.txt", ios::in);
    //Fehler?
    if (!f)
    {
        cout << "Boxes.list.txt konnte nicht geöffnet werden" << endl;
        getchar();
        exit(NULL);
    }
    //und einmal bis zum ende durchlesen
    while (!f.eof())
    {
        //Temporär, um eine zeile zu bearbeiten
        string line;
        Box bx;
        //eine zeile aus der datei lesen
        getline(f, line);

        //id einlesen
        cout << "id:" << (bx.id = line.front());


        //anfang der line sicher abschneiden
        if (line.find(' ') == string::npos)
        {//ups, da fehlt ein Leerzeichen, vergiss diese line
            cout << endl;
            continue;//und mach mit der nächsten weiter
        }
        line = line.substr(line.find_first_of(' '));
        //auf weitere leerzeichen prüfen
        while (line.front() == ' ')
        {
            line = line.substr(1);
        }

        //Maximalgewicht einlesen
        cout << " maxweight:" << (bx.max = atof(line.c_str()));

        //anfang der line sicher abschneiden
        if (line.find(' ') == string::npos)
        {//ups, da fehlt ein Leerzeichen, vergiss diese line
            cout << endl;
            continue;//und mach mit der nächsten weiter
        }
        line = line.substr(line.find_first_of(' '));
        //auf weitere leerzeichen prüfen
        while (line.front() == ' ')
        {
            line = line.substr(1);
        }

        //eigengewicht einlesen
        cout << " weight:" << (bx.weight = atof(line.c_str()));
        cout << " bestätigt" << endl;

        //alle werte eingelesen: in liste einfügen
        ret.push_back(bx);

    }


    //Schön wieder schließen
    f.close();
    return ret;
}

//Rekursive Funktion die alle möglichen Koffer/Gepäck kombinationen ausprobiert
//rückgabe ist eine gefüllte liste, ansonsten eine leere
list<Box> trytofill(list<Box> t_Boxes, list<Package> t_Packages)
{
    //schon alles eingefüllt?
    if (t_Packages.empty())
    {//dann einfach die liste so zurückgeben
        return t_Boxes;
    }

    //Rückgabewert [leer, fals nichts gefunden]
    list<Box> ret;

    //Durchlaufe alle Koffer
    //und versuche dabei den ersten koffer aus der liste einzufügen
    //mit dieser konstellation wird dann weiter getestet
    //bis die liste leer ist
    for (list<Box>::iterator it = t_Boxes.begin(); it != t_Boxes.end(); ++it)
    {
        //Würde das gepäckstück passen?
        if ((*it).test(t_Packages.front()))
        {
            //wenn ja, dann teste weiter
            list<Package> Packages = t_Packages;
            (*it).packages.push_back(Packages.front());
            Packages.pop_front();//aus der für diese box potenziellen liste löschen
            list<Box> possibleBoxes = trytofill(t_Boxes, Packages);
            if (!possibleBoxes.empty())
            {//liste ist nicht leer, also wurde eine lösung gefunden
                return possibleBoxes;
            }
        }//wenn das so nicht passt dann einfach weiter testen
    }

    return ret;
}
//ausgabe in HTML date
void print(list<Box> FinaleListe)
{
    cout << "fertig, speichere in result.html" << endl;
    fstream f;
    f.open("result.html", ios::out);
    if (!f)
    {
        cout << "ERROR OPENING [result.html]" << endl;
    }

    f << "<DOCTYPE HTML>" << endl;
    f << "<html>" << endl;
    f << "<head>" << endl;
    f << "</head>" << endl;
    f << "<body>" << endl;
    f << "<table border=\"2\">" << endl;
    //bit ist die abkürzung für BoxITerator
    for (list<Box>::iterator bit = FinaleListe.begin(); bit != FinaleListe.end(); ++bit)
    {//Jeden koffer durchgehen und die werte ausgeben:
        f << "<tr bgcolor=\"FFa800\">" << endl;
        f << "<td>Koffer:" << (*bit).id << "</td>" << endl << "<td>Maximalgewicht:" << (*bit).max << "</td>" << endl << "<td>Eigengewicht:" << (*bit).weight << "</td>" << endl << "<td>Gesamtgewicht:" << (*bit).allweight() << "</td>" << endl << "<td>Gesamtwert:" << (*bit).allvalue() << "</td>" << endl << "<td>Gepäckstücke:" << (*bit).packages.size() << "</td>" << endl;
        f << "</tr>" << endl;
        //und darunter jedes enthaltene gepäckstück auflisten
        f << "<tr>" << endl;
        f << "<td>Gepäck ID</td>" << endl << "<td colspan=\"3\">Gewicht</td>" << endl << "<td>Wert</td>" << endl;
        f << "</tr>" << endl;
        for (list<Package>::iterator pit = (*bit).packages.begin(); pit != (*bit).packages.end(); ++pit)
        {
            f << "<tr>" << endl;
            f << "<td>" << (*pit).id << "</td>" << endl << "<td colspan=\"3\">" << (*pit).weight << "</td>" << endl << "<td>" << (*pit).value << "</td>" << endl;
            f << "</tr>" << endl;
        }
    }
    f << "</table>" << endl;
    f << "</body>" << endl;
    f << "</html>" << endl;
    f.close();
}

//Haputprogramm
int main(int argc, char* argv[])
{
    //Gepäckliste
    list<Package> Packages = readPackages();
    //Kofferliste
    list<Box> Boxes = readBoxes();
    cout << "------------------------TESTE:" << endl;
    list<Box> FinaleListe = trytofill(Boxes,Packages);
    if (FinaleListe.empty())
    {//leider wurde keine lösung gefunden
        cout << "es gibt keine lösung" << endl;
    }
    else{//ausgeben:
        print(FinaleListe);
    }
    //getchar();
    system("result.html");
    //uuuuund fertig
    return NULL;
}

line = line.substr(line.find_first_of(' '));
while (line.front() == ' ') {
    line = line.substr(1);
 }

line.erase(line.begin(), std::find_if(line.begin(), line.end(), [](wchar_t c) { return !std::isspace(c, locale); }));

while(!f.eof())

while(std::getline(f, line))

const float MAXVALUE = 200.00f;

using std::cout;
using std::getline;
using std::list;
using std::endl;
using std::fstream;