Scribd Logo
Upload

Welcome to Scribd!

  • 82 views

    Bin Packing Problem

    Uploaded by

    ankita wadhwa
    The document discusses the bin packing problem, which aims to minimize the number of bins used to pack items of different weights within each bin's capacity constraint. It provides examples of applications and describes online and offline algorithms for solving bin packing, including Next Fit, First Fit, Best Fit, First Fit Decreasing, and Best Fit Decreasing. The bin packing problem is NP-hard and these algorithms use greedy heuristics to find polynomial-time solutions.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Bin Packing Problem

    Uploaded by

    ankita wadhwa
    82 views11 pages
    The document discusses the bin packing problem, which aims to minimize the number of bins used to pack items of different weights within each bin's capacity constraint. It provides examples of applications and describes online and offline algorithms for solving bin packing, including Next Fit, First Fit, Best Fit, First Fit Decreasing, and Best Fit Decreasing. The bin packing problem is NP-hard and these algorithms use greedy heuristics to find polynomial-time solutions.

    Original Title

    bin packing problem

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the bin packing problem, which aims to minimize the number of bins used to pack items of different weights within each bin's capacity constraint. It provides examples of applications and describes online and offline algorithms for solving bin packing, including Next Fit, First Fit, Best Fit, First Fit Decreasing, and Best Fit Decreasing. The bin packing problem is NP-hard and these algorithms use greedy heuristics to find polynomial-time solutions.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    82 views11 pages

    Bin Packing Problem

    Uploaded by

    ankita wadhwa
    The document discusses the bin packing problem, which aims to minimize the number of bins used to pack items of different weights within each bin's capacity constraint. It provides examples of applications and describes online and offline algorithms for solving bin packing, including Next Fit, First Fit, Best Fit, First Fit Decreasing, and Best Fit Decreasing. The bin packing problem is NP-hard and these algorithms use greedy heuristics to find polynomial-time solutions.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 11

    Bin Packing Problem

    (Minimize number of used


    Bins)
    • Given n items of different weights and bins each of capacity c, assign each
    item to a bin such that number of total used bins is minimized. It may be
    assumed that all items have weights smaller than bin capacity.
    Applications

    • Loading of containers like trucks.


    • Placing data on multiple disks.
    • Job scheduling.
    • Packing advertisements in fixed length radio/TV station breaks.
    • Storing a large collection of music onto tapes/CD’s, etc.
    Online Algorithms

    • These algorithms are for Bin Packing problems where items arrive one
    at a time (in unknown order), each must be put in a bin, before
    considering the next item.
    1. Next Fit:
    When processing next
    item, check if it fits in
    the same bin as the
    last item. Use a new
    bin only if it does not.
    2. First Fit:

    When processing the


    next item, scan the
    previous bins in order
    and place the item in the
    first bin that fits. Start a
    new bin only if it does
    not fit in any of the
    existing bins.
    3. Best Fit:
    The idea is to places
    the next item in the
    *tightest* spot. That
    is, put it in the bin so
    that smallest empty
    space is left.
    Offline Algorithms
    In the offline version, we have
    all items upfront.
    First Fit Decreasing:
    • A trouble with online algorithms is that packing large items is difficult,
    especially if they occur late in the sequence. We can circumvent this
    by *sorting* the input sequence, and placing the large items first.

    • Sort in decreasing order and then apply first fit.

    • Solve this example.


    Best Fit Decreasing:
    • Sort in decreasing order and then apply Best fit.

    • Solve this example.


    • None of the above algorithms gives optimal answers in all scenarios.

    • Bin packing belongs to NP class problems.

    • Therefore we are using different greedy choices (objective functions)


    in different algorithms to obtain a polynomial time solution.

    You might also like