algorithms for placing billboards along a highway with intervals >= 5, using DP or greedy techniques

dp.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <set>

#define ARRAYSIZE(a) (sizeof(a))/(sizeof(a[0]))

using namespace std;

template <class T>
void printVector(const vector<T> & vec) {
    for (T obj : vec)
        cout << setw(2) << obj << " ";
    cout << endl;
}

bool solutionFound(const vector<bool> & available) {
    for (auto b : available) {
        if (b)
            return false;
    }
    return true;
}

int findBest(int value[], const vector<bool> & available) {
    int maxValue = numeric_limits<int>::min();
    int maxIdx = -1;
    for (int i = 0; i < available.size(); i++) {
        if (value[i] > maxValue && available[i]) {
            maxIdx = i;
            maxValue = value[i];
        }
    }

    return maxIdx;
}

void markAsUnavailable(int pos[], vector<bool> & available, const int idx) {
    for (int i = 0; i < available.size(); i++) {
        if (pos[i] > pos[idx] - 5 && pos[i] < pos[idx] + 5) {
            available[i] = false;
        }
        else if (pos[i] >= pos[idx] + 5)
            return;
    }
}

/**
 * Greedy algorithm for choosing spots while maximizing local choices.
 * O(n^2)
 */
set<int> chooseSpotsGreedy(int pos[], int value[], const int N) {
    set<int> spots;
    vector<bool> available(N, true);

    while (! solutionFound(available))
    {
        int best = findBest(value, available);
        markAsUnavailable(pos, available, best);
        spots.insert(best);
        
//        printVector(available);
    }

    return spots;
}

/**
 * Dynamic Programming algorithm for choosing spots while maximizing global value.
 * O(n^2)
 */
set<int> chooseSpotsDP(int pos[], int value[], const int N) {
    
    // DP Matrix
    vector<int> best(N);
    vector<int> previous(N, -1);
    
    for (int i = 0; i < N; i++) {
        best[i] = value[i];
        
        for (int j = i-1; j >= 0; j--) {
            if (pos[i] - pos[j] >= 5 and
                best[j] + value[i] > best[i])
            {
                best[i] = best[j] + value[i];
                previous[i] = j;
                
//                printVector(best);
//                printVector(previous);
//                cout << endl;
            }
        }
    }
    
    
    // Trace-back spots
    set<int> spots;
    int idx = previous.size() - 1;
    
    for (; idx >= 0 && previous[idx] == -1; idx--); // Position idx at first used spot
    
    while (idx >= 0) {
        spots.insert(idx);
        idx = previous[idx];
    }
    
    return spots;
}

void printSpots(const set<int> & spots) {
    cout << "Spots: ";
    for (auto i : spots)
        cout << setw(2) << i << " ";
    cout << endl;
}

void printValue(int value[], const set<int> & spots) {
    int result = 0;
    for (auto i : spots)
        result += value[i];
    cout << "Total value: " << result << endl;
}

// Previous location at distance >= 5km
int previousAvailable(int pos[], const int idx) {
    for (int i = idx - 1; i >= 0; i--) {
        if (pos[idx] - pos[i] >= 5)
            return i;
    }
    return -1;
}

/**
 * DP algorithm for obtaining the max value only, not the locations
 */
int maxValueDP(int pos[], int value[], const int N) {
    vector<int> best(N);

    if (N > 0)
        best[0] = value[0];
    else
        return 0;

    for (int i = 1; i < N; i++) {
        int previous = previousAvailable(pos, i);
        if (value[i] + (previous < 0 ? 0: best[previous]) > best[i-1])
            best[i] = value[i] + (previous < 0 ? 0: best[previous]);
        else
            best[i] = best[i-1];

        printVector(best);
    }

    return best[N-1];
}

int main() {
    int pos[] =     {0, 3, 6, 10, 12, 13, 14, 18, 21};
    int value[] =   {4, 5, 3, 8 , 7 , 1 , 11, 12, 14};
    
    set<int> spots;
    spots = chooseSpotsGreedy(pos, value, ARRAYSIZE(pos));
    cout << "Greedy\n";
    printSpots(spots);
    printValue(value, spots);
    
    spots = chooseSpotsDP(pos, value, ARRAYSIZE(pos));
    cout << "\nDP\n";
    printSpots(spots);
    printValue(value, spots);

    return EXIT_SUCCESS;
}