6

我有一个问题如下：

您将获得重量为 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

我能够使用动态编程方法解决问题；但是，我在这里的问题是确定此类问题的名称以及用于解决该问题的算法。尽管进行了广泛的搜索，但我似乎无法找到它。

对我来说，它类似于装箱问题，除了箱子数量有限，物品数量无限，并且无法在多项式时间内解决。可能是一个离散背包，其中物品重量 = 物品利润和每个物品的无限数量？

4

2 回答 2

3

如果我正确理解了这个问题，

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

您可以使用整数线性规划求解器来解决它。

编辑：正如 Preston Guillot 所指出的，这是一个特殊情况，knapsack problem其中value和mass的项目是相同的。

于 2013-09-13T16:14:40.927 回答
2

正如@dasblinkenlight 评论的那样，这是整数背包问题（或者它的轻微变化，其中每个重量项目的数量w可以达到C / w）。

它有一个解O(n W)，其中n是不同项目的数量，W是容器的容量。这个观察是由于 Sienna，算法设计手册（第 13.10 节背包问题，p428 标题下的所有大小都是相对较小的整数），我基于他对动态规划解决方案的建议来构建下面的算法和代码。

编辑：我刚刚阅读了@progenhard 的评论——是的，这也被称为Change Making Problem。

你要做的是从一个空容器开始，它可以完美地装满任何物品。然后您将每个项目添加到空容器中，以获得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 ]
于 2013-09-13T17:44:14.787 回答