Assignment4_budget_allocation.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5r2msEl9py3R"
      },
      "source": [
        "<b>The Problem Statement</b>:\n",
        "\n",
        "Write a Greedy Algorithm Based program for the following problem:\n",
        "A company is planning to launch a new product. They have a limited budget to spend on marketing and advertising. They need to decide how to allocate their budget to maximize the number of people who will be aware of their product.\n",
        "Marketing Channels:\n",
        "\n",
        "\n",
        "Social Media: Cost - 50,  Reach - 1000 people aware of the product.\n",
        "\n",
        "\n",
        "Email Campaign: Cost - $80, Reach - 1500 people aware of the product.</br>\n",
        "\n",
        "\n",
        "Influencer Collaboration: Cost - $120, Reach - 2500 people aware of the product.\n",
        "\n",
        "Budget Constraint: $200\n",
        "\n",
        "Now, the company wants to allocate their budget to these marketing channels in such a way that they maximize the total number of people aware of their product.\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hi0nFuvoppT9"
      },
      "source": [
        "## The Code"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q1ABUPU7L6em"
      },
      "source": [
        "### Imports"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "i3TtxZ2SL6en"
      },
      "outputs": [],
      "source": [
        "import heapq\n",
        "from pprint import pprint"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hnp5US3YLdEb"
      },
      "source": [
        "### Definition of Heuristic Functions"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "2XryJbWuLdEc"
      },
      "outputs": [],
      "source": [
        "# Define heuristic functions\n",
        "def reach_to_cost_ratio_heuristic(reach, cost):\n",
        "    return round(reach / cost, 3)\n",
        "\n",
        "def reach_heuristic(reach):\n",
        "    return reach"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Using Min Heap"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EULYS1zCLF6l"
      },
      "source": [
        "### Priority Queue Creation"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "id": "dnAv1jaZLF6l"
      },
      "outputs": [],
      "source": [
        "def create_priority_queue(channels, heuristic_function):\n",
        "    \"\"\"\n",
        "    Create a priority queue based on a specified heuristic function.\n",
        "\n",
        "    Args:\n",
        "        channels (list): List of marketing channels as tuples (reach, cost, channel_name).\n",
        "        heuristic_function (function): A function to calculate the priority score for a channel.\n",
        "\n",
        "    Returns:\n",
        "        list: A priority queue of channels.\n",
        "    \"\"\"\n",
        "    priority_queue = []\n",
        "    \n",
        "    if heuristic_function == reach_heuristic:\n",
        "        for channel in channels:\n",
        "            reach, cost, _ = channel\n",
        "            priority_score = heuristic_function(reach)\n",
        "            heapq.heappush(priority_queue, (-priority_score, channel))  # Use negative to prioritize higher scores\n",
        "    \n",
        "    else:\n",
        "        for channel in channels:\n",
        "            reach, cost, _ = channel\n",
        "            priority_score = heuristic_function(reach, cost)\n",
        "            heapq.heappush(priority_queue, (-priority_score, channel))  # Use negative to prioritize higher scores\n",
        "    return priority_queue"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Define the Greedy algorithm"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "Lk7ipyj16Jx8"
      },
      "outputs": [],
      "source": [
        "def greedy_allocation(priority_queue, budget):\n",
        "    \"\"\"\n",
        "    Allocate budget greedily based on the priority queue.\n",
        "\n",
        "    Args:\n",
        "        priority_queue (list): A priority queue of channels.\n",
        "        budget (int): The budget constraint.\n",
        "\n",
        "    Returns:\n",
        "        list: A list of allocated channels.\n",
        "    \"\"\"\n",
        "    allocated_channels = []\n",
        "    remaining_budget = budget\n",
        "\n",
        "    while priority_queue and remaining_budget > 0:\n",
        "        _, channel = heapq.heappop(priority_queue)\n",
        "        _, cost, _ = channel\n",
        "\n",
        "        if cost <= remaining_budget:\n",
        "            allocated_channels.append(channel)\n",
        "            remaining_budget -= cost\n",
        "\n",
        "    return allocated_channels"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Using Max Heap"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Priority Queue Creation"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def create_priority_queue(channels, heuristic_function):\n",
        "    \"\"\"\n",
        "    Create a priority queue based on a specified heuristic function.\n",
        "\n",
        "    Args:\n",
        "        channels (list): List of marketing channels as tuples (reach, cost, channel_name).\n",
        "        heuristic_function (function): A function to calculate the priority score for a channel.\n",
        "\n",
        "    Returns:\n",
        "        list: A priority queue of channels.\n",
        "        \n",
        "        _heapify_max(priority_queue)\n",
        "        _heappop_max(priority_queue)\n",
        "        _heappush_max(priority_queue, (priority_score, channel))\n",
        "    \"\"\"\n",
        "    \n",
        "    priority_queue = []\n",
        "    \n",
        "    if heuristic_function == reach_heuristic:\n",
        "        for channel in channels:\n",
        "            reach, cost, _ = channel\n",
        "            priority_score = heuristic_function(reach)\n",
        "            priority_queue.append((priority_score, channel))\n",
        "            # heapq.heappush(priority_queue, (-priority_score, channel))  # Use max heaps to prioritize higher scores\n",
        "        heapq._heapify_max(priority_queue)\n",
        "    \n",
        "    else: \n",
        "        for channel in channels:\n",
        "            reach, cost, _ = channel\n",
        "            priority_score = heuristic_function(reach, cost)\n",
        "            priority_queue.append((priority_score, channel))\n",
        "            # heapq._heappush_max(priority_queue, (priority_score, channel))  # Use max heaps to prioritize higher scores\n",
        "        heapq._heapify_max(priority_queue)\n",
        "    \n",
        "    return priority_queue"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Define the Greedy algorithm"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def greedy_allocation(priority_queue, budget):\n",
        "    \"\"\"\n",
        "    Allocate budget greedily based on the priority queue.\n",
        "\n",
        "    Args:\n",
        "        priority_queue (list): A priority queue of channels.\n",
        "        budget (int): The budget constraint.\n",
        "\n",
        "    Returns:\n",
        "        list: A list of allocated channels.\n",
        "    \"\"\"\n",
        "    allocated_channels = []\n",
        "    remaining_budget = budget\n",
        "\n",
        "    while priority_queue and remaining_budget > 0:\n",
        "        _, channel = heapq._heappop_max(priority_queue)\n",
        "        _, cost, _ = channel\n",
        "\n",
        "        if cost <= remaining_budget:\n",
        "            allocated_channels.append(channel)\n",
        "            remaining_budget -= cost\n",
        "\n",
        "    return allocated_channels"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TYRZ-f3G6Tpj"
      },
      "source": [
        "### Main function to solve the problem"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "id": "VFUkDQUY6WiX"
      },
      "outputs": [],
      "source": [
        "# Define the marketing channels as tuples (reach, cost, channel_name)\n",
        "social_media = (1000, 50, \"Social Media\")\n",
        "email_campaign = (1500, 80, \"Email Campaign\")\n",
        "influencer_collaboration = (2500, 120, \"Influencer Collaboration\")\n",
        "\n",
        "# Create a list of marketing channels\n",
        "marketing_channels = [social_media, email_campaign, influencer_collaboration]\n",
        "\n",
        "# Budget constraint\n",
        "budget_constraint = 200"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Main function to solve the problem\n",
        "\n",
        "def main():\n",
        "    # Choose a heuristic function (e.g., reach_to_cost_ratio_heuristic or reach_heuristic)\n",
        "    # heuristic_function = reach_heuristic \n",
        "    heuristic_function = reach_to_cost_ratio_heuristic\n",
        "\n",
        "    # Create a priority queue based on the chosen heuristic function\n",
        "    priority_queue = create_priority_queue(marketing_channels, heuristic_function)\n",
        "    # print(\"-\"*160,\"\\n\",\"Priority Queue:\",priority_queue,\"\\n\",\"-\"*160)\n",
        "    print(\"-\"*50,\"\\n\",f\"Priority Queue using {heuristic_function}:\")\n",
        "    pprint(priority_queue)\n",
        "    print(\"-\"*50,\"\\n\")\n",
        "\n",
        "    # Allocate budget greedily\n",
        "    allocated_channels = greedy_allocation(priority_queue, budget_constraint)\n",
        "\n",
        "    # Print the allocated channels and their details\n",
        "    total_reach = sum(reach for reach, _, _ in allocated_channels)\n",
        "    total_cost = sum(cost for _, cost, _ in allocated_channels)\n",
        "\n",
        "    print(\"Allocated Channels:\")\n",
        "    for reach, cost, channel_name in allocated_channels:\n",
        "        print(f\"{channel_name}: Reach - {reach}, Cost - ${cost}\")\n",
        "\n",
        "    print(f\"Total Reach: {total_reach}\")\n",
        "    print(f\"Total Cost: ${total_cost}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 11,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "-------------------------------------------------- \n",
            " Priority Queue using <function reach_to_cost_ratio_heuristic at 0x00000217B3C6B760>:\n",
            "[(-20.833, (2500, 120, 'Influencer Collaboration')),\n",
            " (-18.75, (1500, 80, 'Email Campaign')),\n",
            " (-20.0, (1000, 50, 'Social Media'))]\n",
            "-------------------------------------------------- \n",
            "\n",
            "Allocated Channels:\n",
            "Influencer Collaboration: Reach - 2500, Cost - $120\n",
            "Social Media: Reach - 1000, Cost - $50\n",
            "Total Reach: 3500\n",
            "Total Cost: $170\n"
          ]
        }
      ],
      "source": [
        "if __name__ == \"__main__\":\n",
        "    main()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.10.9"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}