2018-05-29

Okay, working through the algorithmic toolbox class. It took me a day to work out the fractional knapsack problem. It took a couple read throughs of the forum threads, but I finally figured out my problem.

I was trying to compute the best value by iterating over the list of items and computing something to the effect of

Item
max_value(int capacity, Item item)
{
    if (item.weight == 0) {
        item.value = 0;
        return item;
    }
    if (capacity >= item.weight) {
        return item;
    }

    auto weight = capacity;
    double frac = static_cast<double>(weight) / static_cast<double>(item.weight);

    item.value *= frac;
    item.weight = weight;
    return item;
}

The key insight was to add another field to the items representing the value to weight ratio, sort the vector of items, and keep taking items from the top until there's no room left. Once I did that, the problem passed.

Thinking about sorting the list made solving the next problem easier: given two lisys of numbers (a and b), find the maximum value of the sum of products of pairs. For example, given a ← (1, 3, -5) and b ← (-2, 4, 1), the optimum pairing is 3x4 + 1x1 + -5x-2. The way to do this is to sort both lists, multiply each pair, and add the results together.

It's fun solving problems again, even if they feel a bit contrived.


Tags: ,