当我想要选择尽可能填满容器的项目时，该怎么称呼？我应该使用哪种算法？

当我想要选择尽可能填满容器的项目时，该怎么称呼？我应该使用哪种算法？

正如@dasblinkenlight所评论的那样，这是整数背负问题（或其上的一些细微变化，每一项重量的数量

w

最多可以达到

C / w

）。

它在中有一个解决方案

O(n W)

，其中

n

是不同项目的数量，并且

W

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

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

您要做的是从一个空的容器开始，该容器可以完全装满任何物品。然后，您将每个项目都添加到空容器中，以获取

n

新的已填充容器，即

n

每个容器仅包含一个项目。然后，将物品添加到新容器中，然后冲洗并重复直到您超过最大容量

W

。因此，可以

n

选择最大

W

容量

O(nW)

。

向后浏览您的容器以找到已完全填充的最大容器很简单，但是在下面的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 ]