project.cpp

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

// ---------------- CLEAR SCREEN ----------------
void clearScreen()
{
    cout << "\033[2J\033[1;1H";
}

// ---------------- WELCOME PAGE ----------------
void displayWelcomePage()
{
    cout << "----------------------------------------------" << endl;
    cout << "----------------------------------------------" << endl;
    cout << "||                                          ||" << endl;
    cout << "||                                          ||" << endl;
    cout << "||   WELCOME TO DELIVERY LOGISTIC PATH      ||" << endl;
    cout << "||                 FINDER                   ||" << endl;
    cout << "||                                          ||" << endl;
    cout << "----------------------------------------------" << endl;
    cout << "----------------------------------------------" << endl;

    cout << "Press Enter to proceed to the main menu..." << endl;
    cin.ignore();
    cin.get();
    clearScreen();
}

// ---------------- TASK SCHEDULING ----------------
struct Job
{
    int id;
    int deadline;
    int penalty;
};

void TaskScheduling(int numOrders)
{
    cout << "All deadlines should be entered in intervals of 10 minutes." << endl;

    vector<Job> jobs(numOrders);

    for (int i = 0; i < numOrders; i++)
    {
        cout << "Enter deadline for order " << i + 1 << ": ";
        cin >> jobs[i].deadline;
        jobs[i].id = i + 1;
    }

    for (int i = 0; i < numOrders; i++)
    {
        cout << "Enter penalty percentage if late (for order " << i + 1 << "): ";
        cin >> jobs[i].penalty;
    }

    sort(jobs.begin(), jobs.end(), [](Job a, Job b)
         { return a.penalty > b.penalty; });

    int maxDeadline = 0;
    for (auto j : jobs)
        maxDeadline = max(maxDeadline, j.deadline / 10);

    vector<int> slot(maxDeadline + 1, -1);

    int lateTasksCount = 0;

    for (auto j : jobs)
    {
        int d = j.deadline / 10;
        bool scheduled = false;

        for (int i = d; i > 0; i--)
        {
            if (slot[i] == -1)
            {
                slot[i] = j.id;
                scheduled = true;
                break;
            }
        }

        if (!scheduled)
            lateTasksCount++;
    }

    cout << endl
         << "Orders should be delivered in the following order: " << endl;

    for (int i = 1; i <= maxDeadline; i++)
    {
        if (slot[i] != -1)
            cout << "Order " << slot[i] << " ";
    }

    cout << endl
         << "Number of orders delivered late: " << lateTasksCount << endl
         << endl;
}

// ---------------- KNAPSACK ----------------
void printKnapSack(int maxWeight, int numItems)
{
    vector<int> profit(numItems), weight(numItems);

    for (int i = 0; i < numItems; i++)
    {
        cout << "Enter order value for order no " << i + 1 << ": ";
        cin >> profit[i];
    }

    for (int i = 0; i < numItems; i++)
    {
        cout << "Enter number of items in order " << i + 1 << ": ";
        cin >> weight[i];
    }

    vector<vector<int>> dp(numItems + 1, vector<int>(maxWeight + 1, 0));

    for (int i = 1; i <= numItems; i++)
    {
        for (int w = 0; w <= maxWeight; w++)
        {
            if (weight[i - 1] <= w)
                dp[i][w] = max(profit[i - 1] + dp[i - 1][w - weight[i - 1]], dp[i - 1][w]);
            else
                dp[i][w] = dp[i - 1][w];
        }
    }

    cout << endl
         << "To achieve maximum profit, carry the following orders:" << endl;

    int w = maxWeight;
    for (int i = numItems; i > 0; i--)
    {
        if (dp[i][w] != dp[i - 1][w])
        {
            cout << "Order value: " << profit[i - 1] << endl;
            w -= weight[i - 1];
        }
    }
}

// ---------------- TSP ----------------
void tsp(int graph[10][10], bool completed[10], int numHouses, int cost, int pos, int count, int &minCost)
{
    if (count == numHouses && graph[pos][0])
    {
        minCost = min(minCost, cost + graph[pos][0]);
        return;
    }

    for (int i = 0; i < numHouses; i++)
    {
        if (!completed[i] && graph[pos][i])
        {
            completed[i] = true;
            tsp(graph, completed, numHouses, cost + graph[pos][i], i, count + 1, minCost);
            completed[i] = false;
        }
    }
}

// ---------------- MENU ----------------
int displayMenu()
{
    int choice;
    cout << endl
         << "---- Welcome User ----" << endl;
    cout << "You have 3 choices to deliver the orders. Choose accordingly and enter the details asked:" << endl;
    cout << "1. Find the best economic way to deliver all the orders (TSP Algorithm)" << endl;
    cout << "2. Check which orders can be delivered for maximum profit with quantity constraint (Knapsack Algorithm)" << endl;
    cout << "3. Determine the maximum number of orders to be delivered without incurring penalties (Task Scheduling)" << endl;
    cout << "Enter your choice (1-3): ";
    cin >> choice;

    while (choice < 1 || choice > 3)
    {
        cout << "Invalid choice. Please enter a number between 1 and 3: ";
        cin >> choice;
    }
    return choice;
}

// ---------------- MAIN ----------------
int main()
{
    displayWelcomePage();

    char runAgain = 'y';

    while (runAgain == 'y' || runAgain == 'Y')
    {
        int userChoice = displayMenu();

        if (userChoice == 1)
        {
            int costMatrix[10][10], numHouses, minCost = INT_MAX;
            cout << "Enter the number of houses: ";
            cin >> numHouses;
            numHouses++;

            bool completed[10] = {false};
            completed[0] = true;

            cout << "Enter the Cost Matrix (all distances in km):" << endl;

            for (int i = 0; i < numHouses; i++)
            {
                for (int j = 0; j < numHouses; j++)
                {
                    if (i != j)
                    {
                        if (i == 0)
                            cout << "Enter distance from delivery point (Dispatch Hub) to house " << j << ": ";
                        else if (j == 0)
                            cout << "Enter distance from house " << i << " to Dispatch Hub: ";
                        else
                            cout << "Enter distance from house " << i << " to house " << j << ": ";

                        cin >> costMatrix[i][j];
                    }
                    else
                    {
                        costMatrix[i][j] = 0;
                    }
                }
            }

            cout << endl << "The distance matrix is:";
            for (int i = 0; i < numHouses; i++)
            {
                cout << endl;
                for (int j = 0; j < numHouses; j++)
                    cout << "\t" << costMatrix[i][j];
            }
            cout << endl;

            tsp(costMatrix, completed, numHouses, 0, 0, 1, minCost);

            cout << "Minimum distance to deliver all orders = " << minCost << " km" << endl;
        }
        else if (userChoice == 2)
        {
            int numOrders, maxWeight;
            cout << "Enter number of orders: ";
            cin >> numOrders;
            cout << "Enter the maximum weight capacity: ";
            cin >> maxWeight;

            printKnapSack(maxWeight, numOrders);
        }
        else if (userChoice == 3)
        {
            int numOrders;
            cout << "Enter number of orders: ";
            cin >> numOrders;

            TaskScheduling(numOrders);
        }

        cout << "Would you like to run the program again? (y/n): ";
        cin >> runAgain;
    }

    cout << "Thank you for using the delivery management system. Goodbye!" << endl;
    return 0;
}