The Algorithm Design Manual (3rd) Exercise Solution 'E3-25'

Table of Contents

Introduction
Repository
Exercise 3-25
- Question
- Solution

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-25

Question

In the bin-packing problem, we are given n objects, each weighing at most 1 kilogram. Our goal is to find the smallest number of bins that will hold the n objects, with each bin holding 1 kilogram at most.

The best-fit heuristic for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the n weights w1, w2, ..., wn and outputting the number of bins used) in $O(n log n)$ time.
Repeat the above using the worst-fit heuristic, where we put the next object into the partially filled bin with the largest amount of extra room after the object is inserted.

Solution

Best fit

On storing w_i item, We search an existing bin whose amount of room is the smallest of the ones whose remaining room is >= w_i in binary search tree. It requires descending the tree and quering each node about the condition. It costs $O(logn)$ .

Then delete the node and insert a new one whose remaining room is (previous value - w_i). It also costs $O(logn)$ .

The total cost is $O(nlogn)$ .

Below is C++ implementation.

#include "./best-fit.h"

#include <set>
#include <stdexcept>
#include <vector>

int bin_packing_best_fit(std::vector<int> weights) {
    // construct the tree which accomodates the rest spaces of bins
    std::multiset<int> spaces{};  // unit in gram
    for (int i = 0; i < weights.size(); ++i) {
        if (weights[i] < 0 || 1000 < weights[i])
            throw std::invalid_argument("invalid weight");
        // place the object of weight[i]
        //  into the first space that is greater than or equal to the weight
        // if there are no such space, add a new bin
        auto it{spaces.lower_bound(weights[i])};
        if (it == spaces.end()) {
            spaces.insert(1000 - weights[i]);

        } else {
            int new_space{*it - weights[i]};
            spaces.erase(it);
            spaces.insert(new_space);
        }
    }
    return spaces.size();
}

Worst fit

Roughly the same as Best fit case. But we search a bin whose remaining room is the largest of all.
The total cost is $O(nlogn)$ .

Below is C++ implementation.

#include <set>
#include <stdexcept>
#include <vector>

#include "./worst-fit.h"
int bin_packing_worst_fit(std::vector<int> weights) {
    // construct the tree which accomodates the rest spaces of bins
    std::multiset<int> spaces{};
    for (int i = 0; i < weights.size(); ++i) {
        if (weights[i] < 0 || 1000 < weights[i])
            throw std::invalid_argument("invalid weight");
        // place the object of weight[i]
        //  into the largest space
        // if there are no space available, add a new bin
        auto it{spaces.rbegin()};
        if (it == spaces.rend() || *it < weights[i]) {
            spaces.insert(1000 - weights[i]);

        } else {
            int new_space{*it - weights[i]};
            spaces.erase(std::next(it).base());
            spaces.insert(new_space);
        }
    }
    return spaces.size();
}

Comparison of both strategies

From the comparison in the code below, the proportion of winning between Best fit and Worst fit, and the case resulting in "Even" in the experiment for randomly weighted items is:

best_fit_wins: 9998
worst_fit_wins: 0
even: 2

So if the items' weight is at random, the better strategy is Best fit.

Below is C++ implementation.

#include <iostream>
#include <vector>

#include "../../../../util/random/random.h"
#include "../best-fit/best-fit.h"
#include "../worst-fit/worst-fit.h"

int main(int argc, char const *argv[]) {
    int best_fit_wins{0};
    int worst_fit_wins{0};
    int even{0};
    for (int i = 0; i < 10000; i++) {
        std::vector<int> v{};
        for (int j = 0; j < 100; j++) {
            v.push_back(Random::get(1, 1000));
        }
        int bf_result{bin_packing_best_fit(v)};
        int wf_result{bin_packing_worst_fit(v)};
        if (bf_result < wf_result)
            ++best_fit_wins;
        else if (bf_result == wf_result)
            ++even;
        else
            ++worst_fit_wins;
    }
    std::cout << "best_fit_wins: " << best_fit_wins
              << " worst_fit_wins: " << worst_fit_wins << " even: " << even
              << "\n";
    return 0;
}