最大填充袋子的算法（不是背包0/1） [英] Algorithm for Filling bag maximally (this is not the knapsack 0/1)

问题描述

我正在执行某些任务，需要我解决以下算法问题：

---

-您有项目集合（其权重）：[w1，w2，... ，wn]

-您有一个袋子，重量为：W

-需要用给定项目的子集最大程度地装满袋子（尽可能多地装满） 。

---

因此，此不是问题背包0/1，因为我们只处理权重（我们只有一个参数）用于项目）。因此，我认为它可能有一个解决方案（背包是NP完全的）或某种算法，其给出的结果大致正确。

请不要建议我贪婪算法，因为我认为应该有一种算法可以提供更好的结果。我认为这应该是一种使用动态编程的算法。

在此先感谢您：）

解决方案

在这种特殊情况下，您可以通过最小化包装袋中的可用空间并因此将重量作为值来获得最大的收益。这个问题通常称为

在每个步骤中，您都尝试在先前的元素集和新元素之间找到最大值（不超过袋子的容量）

子集和问题的C ++实现，以回答问题：在给定这些元素的情况下，我是否可以完全装满袋子？并且驱动程序遵循

  bool ssp（const vector< int& v，const int& N）{
 
 vector< vector< int> m（v.size（）+ 1 / *基于1的* /，
 vector （N + 1 / *基于1的* /，0））; 
 
 //上面的行还处理了基数
的初始化//情况f（i，0）= 0和f（0，b）= 0 
 
 for（int i = 1; i< = v.size（）; ++ i）{//对于元素
的每个子集（int b = 1; b< = N; + + b）{//对于每个子容量
 int opt1 = m [i-1] [b]; 
 int opt2 = -1; 
 if（b-v [i-1]> = 0）{//没有缓存以保持可读性
 opt2 = m [i-1] [b-v [i-1]] + v [i-1]; 
如果（opt2> b）
 opt2 = -1; //不允许
} 
 m [i] [b] = max（opt1，opt2）; 
} 
} 
 
回报（m [v.size（）] [N] == N）; 
} 
 
 int main（）{
 
 const vector< int> v = {1，3，7，4}; 
 const int N = 11; 
 
 cout<< 子集总和问题可以通过给定的输入来解决： 
<< boolalpha<< ssp（v，N）; // true 
 
返回0; 
} 
  

复杂度为 O（N⋅I）其中， I 是起始集中的元素数。这是伪多项式复杂度。

来源：背包问题

I am working on some task which requires from me to solve the following algorithmic problem:

---

- You Have collection of items (their weights): [w1, w2, ..., wn]
- And You have a bag which weight is: W
- It is Needed to fill the bag maximally (fill as much as possible) with the subset of given items.

---

So this is not "Knapsack 0/1" problem, as we deal only with weights (we have only one parameter for item). Therefore I assume that it might have a solution (Knapsack is NP-complete) or some kind of algorithm which gives approximately correct result.

Please don't suggest me "greedy algorithms", because I believe that there should be an algorithm which gives better results. I think that it should be an algorithm which uses "dynamic programming".

Thank you in advance :)

解决方案

In this particular instance you get maximum benefit by minimizing the free space in the bag and therefore by considering weight as a value. This problem is commonly referred to as subset sum problem and is a particular case of knapsack problems family.

The DP relation looks like the following

where at each step you try to find the maximum value (which does not exceed the bag's capacity) among the previous elements set plus the new element

A C++ implementation of the subset sum problem to answer the question "can I fill the bag entirely given these elements?" and driver follows

bool ssp(const vector<int>& v, const int& N) {

  vector<vector<int>> m( v.size() + 1 /* 1-based */,
                         vector<int>(N + 1 /* 1-based */, 0) );

  // The line above also took care of the initialization for base
  // cases f(i,0) = 0 and f(0,b) = 0

  for (int i = 1; i <= v.size(); ++i) { // For each subset of elements
    for (int b = 1; b <= N; ++b) { // For each subcapacity
      int opt1 = m[i - 1][b];
      int opt2 = -1;
      if (b - v[i - 1] >= 0) { // No caching to keep this readable
        opt2 = m[i - 1][b - v[i - 1]] + v[i - 1];
        if (opt2 > b)
          opt2 = -1; // Not allowed
      }
      m[i][b] = max(opt1, opt2);
    }
  }

  return (m[v.size()][N] == N);
}

int main() {

  const vector<int> v = { 1, 3, 7, 4 };
  const int N = 11;

  cout << "Subset sum problem can be solved with the given input: "
       << boolalpha << ssp(v, N); // true

  return 0;
}

The complexity is O(N⋅I) where I is the number of elements in the starting set. This is a pseudopolynomial complexity.

Source: Knapsack problem

这篇关于最大填充袋子的算法（不是背包0/1）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！