Algorithm for spending x points on y things divided by n people

Question

I'm trying to devise an algorithm to spend a given amount of points on a randomly generated list of items each with their own cost in a way that results in having a number of items that is divisible by a given value (the number of points given is always divisible by this). Each item must be represented as equally as possible.

Points: 12
Divisor: 6
Items: Foo (1) & Bar (3)

The optimal result would be 3 Foo and 3 Bar (12 total points and 6 items).

That could be achieved by filling the space alternately starting with the smallest item but that algorithm won't work for other permutations of the starting values or if there are more items to spend points on, some of which may have the same value as other items but must be represented equally in the final result.

The algorithm can result in spending less points than are available but never more. There may not always be a 1 cost item to fill in any remainders.

Another example I can't solve...

Points: 24
Divisor: 8
Items: Foo (1), Nacho (1) , Pizza(2), Bar (3), Cake (4)

Just spending all of the points is easy but spending it in such a way that you end with a specific number of items that can be divided between the divisor has had me scratching my head all day.

Answer 1

This sounds like a more complex version of the classic "animal legs" problem. Except in that case, you only have two animals to deal with, so you could work it out using elementary maths ("every time I swap a cow for a chicken, I get two more legs...").

But in this case you have more variables, so you'll need to resort to the algorithmic way. Recall that in the animal legs problem, you get something like this:

number_of_chickens2 + number_of_cows4 = number_of_legs

number_of_chickens + number_of_cows = number_of_heads

number_of_legs and number_of_heads are known, so substitute the equations into each other.

In your example, there are many more variables - more "animals" - which looks something like this:

number_of_foo + number_of_nachos + number_of_pizzas2 + number_of_bars3 + number_of_cakes*4 = 24

number_of_foo + number_of_nachos + number_of_pizzas + number_of_bars + number_of_cakes = 8

A typical way to solve this is to express this as a matrix and perform row reduction on it, the simplest method of which (both by hand and by computer algorithm) is Gaussian elimination. You may have been taught this in high school.

| 1 1 2 3 4 | 24 |
| 1 1 1 1 1 | 8  |

(swap row1 and row2)
| 1 1 1 1 1 | 8  |
| 1 1 2 3 4 | 24 |

(row2 = row2 - row1)
| 1 1 1 1 1 | 8  |
| 0 0 1 2 3 | 16 |

(row1 = row1 - row2)
| 1 1 0 -1 -2 | -8 |
| 0 0 1  2  3 | 16 |

Now that the equations are in reduced row echelon form, you can start plugging in values to see which ones work. Note that your matrix isn't completely reduced, which tells you there are many possible solutions.

Let's start with row 2: it is basically saying: number_of_pizzas + number_of_bars*2 + number_of_cakes*3 = 16. Obviously keep in mind that you can't have negative numbers of anything, which implies that you can't have more than 8 of anything. With that in mind, we can plug in 8 for the number of bars, which means 0 pizzas and 0 cakes:

01 + 82 + 0*3 = 16

Now put those values into row 1:

number_of_foo1 + number_of_nachos1 + 00 + 8-1 + 0*-2 = -8

number_of_foo + number_of_nachos = 0

Now we have our first solution: 8 bars.

Going back to the matrix, since any set of values that satisfies those row equations work, we can also try 5 cakes, which forces us to choose 1 pizza:

11 + 02 + 5*3 = 16

Into row 1:

number_of_foo1 + number_of_nachos1 + 10 + 0-1 + 5*-2 = -8

number_of_foo + number_of_nachos = 2

Now we have a second set of solutions, as long as the number of foo and nachos total 2 (they cost the same so it doesn't matter), and there's 1 pizza and 5 cakes.

Let's try one more, just to get the hang of it. We can have 4 cakes, and 2 bars, which leaves 0 pizzas:

01 + 22 + 4*3 = 16

Into row 1:

number_of_foo1 + number_of_nachos1 + 00 + 2-1 + 4*-2 = -8

number_of_foo + number_of_nachos = 2

Again, we have 2 foo-or-nachos, but this time also 2 bars and 4 cakes.

You may be wondering why we're guessing the values at the end - isn't there an algorithmic way to solve this? Sure, there is, it's called integer programming which is unfortunately NP-hard. So guessing, or going through all the possibilities, should be good enough.

Answer 2

When you're dealing with small numbers, sometimes the brute-force approach is best. In this case, you can simply try all combinations of items and return the ones where the point sum is right.

The trick is to work out all the combinations (a.k.a. multiset), and in your case, repeat the whole process but with a multiple of your divisor, until the number of things is too high, because even if you only choose your smallest-point item only, the points will exceed your target.

To make this more concrete, consider your second example; first we try picking 8 items that total 24 points. Try again for 16 items, and for 24 items. Stop after this, because after 24 even if you pick only the smallest point items (Foo or Nacho), you would exceed your point target.

Here's some sample code; you can find ways to generate multisets ("combinations with repetitions") on rosettacode.

var items = [['Foo', 1], ['Nacho', 1], ['Pizza', 2], ['Bar', 3], ['Cake', 4]];
var smallestPoint = 1;
var points = 24;
var divisor = 8;

function pick(n, got, pos, from, out) {
    if (got.length == n) {
        out.push(got.slice());
        return;
    }
    for (var i = pos; i < from.length; i++) {
        got.push(from[i]);
        pick(n, got, i, from, out);
        got.pop();
    }
}

function itemPointsEqual(items, points) {
    var sum = 0;
    for (var i = 0; i < items.length; i++) {
        sum += items[i][1];
    }
    return sum == points;
}

function countItems(items) {
    var counts = {};
    for (var i = 0; i < items.length; i++) {
        var name = items[i][0];
        counts[name] = counts[name] ? counts[name] + 1 : 1;
    }
    var countNames = [];
    for (var name in counts) {
        countNames.push(counts[name] + ' ' + name + 's');
    }
    return countNames.join(', ');
}

function disp(x) {
    var e = document.createElement('p');
    e.innerHTML = x;
    document.getElementsByTagName('body')[0].appendChild(e);
}

for (var total = divisor; total <= points / smallestPoint; total += divisor) {
    var combos = [];
    pick(total, [], 0, items, combos);
    for (var i = 0; i < combos.length; i++) {
        if (itemPointsEqual(combos[i], points)) {
            disp('Combination: ' + countItems(combos[i]) +
                '; total items: ' + total);
        }
    }
}