What's it called when I want to choose items to fill container as full as possible - and what algorithm should I use?

Question

I have a problem as follows:

You are given item types of weight w1, w2, w3, .... wn; each item of these types is infinite in quantity.

You have a container capable of carrying weight W.

Find the combination(s) of items with greatest sum of weights that will fit in the container without exceeding the maximum weight W.

So for example:

I have three types of items with weights:

• w = 5
• w = 10
• w = 20

And I have a container of Weight capacity: W = 25

Possible solutions would be:

• 5 items of w = 5, 0 items of w = 10, 0 items of w = 20;
• 1 item of w = 5, 0 items of w = 10, 1 item of w = 20

I was able to solve the problem using a dynamic programming approach; however, my issue here is identifying the name of this type of problem and the algorithm one would use to solve it. I just can't seem to put a finger on it despite extensive searching.

To me, it resembles a bin-packing problem, except with limited number of bins, infinite amount of items, and would not be solvable in polynomial time. Possibly a discrete knapsack with item weight = item profit and infinite number of each item?

Answer 1

If I have understood the problem correctly,

For xi belongs to {0,1, ... infinity} (i = 1 to n)
Maximize summation(wixi) (i = 1 to n)
subject to:
summation (wixi) <= W

You can solve it using an Integer Linear Programming Solver.

EDIT: as pointed out by Preston Guillot, it is a special case of knapsack problem where the value and mass of the items are the same.

Answer 2

As @dasblinkenlight comments, this is the integer knapsack problem (or a slight variation on it where the number of each item of weight w can be upto C / w).

It has a solution in O(n W), where n is the number of different items, and W is the capacity of the container. This observation is due to Sienna, The Algorithm Design Manual (section 13.10 Knapsack problem, p428 under the heading Are all the sizes relatively small integers), and I've based the algorithm and code below on his suggestion for a dynamic programming solution.

Edit: I just read @progenhard's comment -- yes, this is also known as the Change Making Problem.

What you do is start off with an empty container, which can be filled perfectly with no items. And then you take each item and add that to the empty container, to get n new filled containers, i.e. n containers each containing exactly one item. You then add items to the new containers, and rinse and repeat until you have exceeded your maximum capacity W. There are n choices for a maximum of W capacities, hence O(n W).

It's a simple matter to look backwards through your containers to find the largest one that has been perfectly filled, but in the C++ code below I just print out the whole array of containers.

#include <iostream>
#include <vector>

using std::vector;

int main(int argc, char* argv[])
{
    const int W = 25;
    const int ws[] = { 5, 10, 20 };

    const int n = sizeof(ws) / sizeof(int);

    typedef std::vector<int> wgtvec_t;
    typedef std::vector<wgtvec_t> W2wgtvec_t; 

    // Store a weight vector for each container size
    W2wgtvec_t W2wgtvec(W +1);

    // Go through all capacities starting from 0
    for(int currCapacity=0; currCapacity<W; ++currCapacity) {
        const wgtvec_t& currWgtvec = W2wgtvec[currCapacity];
        // If we have a solution for capacity currCapacity, find other solutions
        if (currCapacity==0 || !currWgtvec.empty()) {
            for(int i=0; i<n; ++i) {
                const int increaseCapacity = ws[i];
                const int newCapacity = currCapacity + increaseCapacity;
                if (newCapacity <= W) {
                    wgtvec_t& newWgtvec = W2wgtvec[newCapacity];
                    // Update new capacity if it doesn't already have a solution
                    if (newWgtvec.empty()) {
                        newWgtvec = currWgtvec;
                        newWgtvec.push_back(increaseCapacity);
                    }
                }
            }
        }
    }

    // Print out all our solutions
    for(int currCapacity=1; currCapacity<=W; ++currCapacity) {
        using std::cout;
        const wgtvec_t& currWgtvec = W2wgtvec[currCapacity];
        if (!currWgtvec.empty()) {
            cout << currCapacity << " => [ ";
            for(wgtvec_t::const_iterator i=currWgtvec.begin(); i!=currWgtvec.end(); ++i) {
                cout << *i << " ";
            }
            cout << "]\n";
        }
    }

    return 0;
}

The output for this case is

5 => [ 5 ]
10 => [ 10 ]
15 => [ 5 10 ]
20 => [ 20 ]
25 => [ 5 20 ]

With a more interesting problem

    const int W = 26;
    const int ws[] = { 3, 5, 10, 20 };

the output is

3 => [ 3 ]
5 => [ 5 ]
6 => [ 3 3 ]
8 => [ 3 5 ]
9 => [ 3 3 3 ]
10 => [ 10 ]
11 => [ 3 3 5 ]
12 => [ 3 3 3 3 ]
13 => [ 3 10 ]
14 => [ 3 3 3 5 ]
15 => [ 5 10 ]
16 => [ 3 3 10 ]
17 => [ 3 3 3 3 5 ]
18 => [ 3 5 10 ]
19 => [ 3 3 3 10 ]
20 => [ 20 ]
21 => [ 3 3 5 10 ]
22 => [ 3 3 3 3 10 ]
23 => [ 3 20 ]
24 => [ 3 3 3 5 10 ]
25 => [ 5 20 ]
26 => [ 3 3 20 ]