正如@dasblinkenlight所评论的那样，这是整数背负问题（或其上的一些细微变化，每一项重量的数量w最多可以达到C / w）。

它在中有一个解决方案O(n W)，其中n是不同项目的数量，并且W是容器的容量。这种观察是由于Sienna
算法设计手册（第13.10节背包问题，标题为p428的 所有尺寸都是相对较小的整数
）的缘故，因此，我根据以下他对动态编程解决方案的建议建立了算法和代码。

编辑 ：我只读了@progenhard的评论-是的，这也称为“
变更制作问题”。

您要做的是从一个空的容器开始，该容器可以完全装满任何物品。然后，您将每个项目都添加到空容器中，以获取n新的已填充容器，即n每个容器仅包含一个项目。然后，将物品添加到新容器中，然后冲洗并重复直到您超过最大容量W。因此，可以n选择最大W容量O(n W)。

向后浏览您的容器以找到已完全填充的最大容器很简单，但是在下面的C ++代码中，我只是打印出整个容器数组。

#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;
}

这种情况的输出是

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

还有一个更有趣的问题

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

输出是

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 ]