当我想选择尽可能充满容器的物品时它叫什么 - 我应该使用什么算法？

Question

我有一个问题如下:

给你的物品类型的重量w1,w2,w3,.... wn; 这些类型的每个项目数量都是无限的.

你有一个能够承载重量W的容器.

找到适合容器的最大重量总和的项目组合,不超过最大重量W.

例如:

我有三种带有重量的物品:

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

我有一个重量容量容器:W = 25

可能的解决方案是:

• 5项w = 5,0项w = 10,0项w = 20;
• 1项w = 5,0项w = 10,1项w = 20

我能够使用动态编程方法解决问题; 但是,我的问题是确定这类问题的名称以及用于解决问题的算法.尽管进行了广泛的搜索,我似乎无法用手指指着它.

对我来说,它类似于bin-packing问题,除了有限数量的bin,无限量的项目,并且在多项式时间内无法解决.可能是一个离散的背包,项目重量=项目利润和每个项目的无限数量？

Answer 1

正如 @dasblinkenlight 评论的那样，这是整数背包问题（或者稍有变化，其中每项重量的数量w最多可达C / w）。

它有一个解O(n W)，其中n是不同物品的数量，W是容器的容量。这一观察源自 Sienna，《算法设计手册》（第 13.10 节背包问题，第 428 页标题下的所有尺寸都相对较小的整数），并且我基于他对动态规划解决方案的建议来编写下面的算法和代码。

编辑：我刚刚读了 @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 ]