什么叫时，我想选择的项目，以填补容器尽可能充分 - 我应该用什么算法？ [英] What's it called when I want to choose items to fill container as full as possible - and what algorithm should I use?

问题描述

我有一个问题如下：

正在给定项目类型配重W1，W2，W3，... WN;的每个项目   这些类型是无限数量。

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

您必须能够携带重量W的容器。

You have a container capable of carrying weight W.

查找物品的组合（S）与权重最大的一笔是   将适合在容器中不超过最大重量W

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

因此​​，例如：

我有三个类型的项目，配重块：

I have three types of items with weights:

  
• 在W = 5
  
• 在W = 10
  
• 在W = 20
  

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

和我有承重能力的容器：   W = 25

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

可能的解决办法是：

  
• 5项W = 5，W 0项= 10，0项W = 20;
  对W = 5，W 0项= 10，W的1项= 20
• 1个项目   

• 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?

推荐答案

由于@dasblinkenlight的意见，这是整数背包问题（或在其上有轻微的变形，其中权重的每个项目的数量W¯¯ 可高达 C / W ）。

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).

它在的解决方案为O（n W），其中 N 是不同的项目数，和是W 是容器的容量。这种现象是由于西耶娜，的算法设计手册（第13.10背包问题的标题下，P428的是否所有的尺寸相对较小的整数的），我已经根据下面的算法和code对他的建议进行动态编程解决方案。

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.

修改的：我刚刚看了@ progenhard的评论 - 是的，这也被称为的更改决策问题。

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

你做的是一个空的容器，它可以完美地与任何项目填补开始。然后你把每个项目，并添加到空的容器，要获得 N 新填充的容器，即 N 集装箱每个正好包含一个项目。然后，添加项目到新的容器，并冲洗和重复，直到你已经超出最大容量是W 。有 N 选择最多的是W 的能力，因此为O（n W）。

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).

这是一个简单的事情向后看通过你的容器，找到最大的一个已被完全填补，但在C ++ code下面我就打印出容器的整个阵列。

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

有此情况下的输出是

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 ]

这篇关于什么叫时，我想选择的项目，以填补容器尽可能充分 - 我应该用什么算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！