最大填充袋子的算法(这不是背包 0/1)

Question

我正在做一些需要我解决以下算法问题的任务:

---

- 你收集了元素(它们的重量):[w1, w2, ..., wn]
- 你有一个包，重量是:W
- 需要用给定项目的子集最大限度地填充袋子(尽可能多地填充)。

---

所以这不是“背包 0/1”问题，因为我们只处理重量(我们只有一个项目参数)。因此，我假设它可能有一个解决方案(Knapsack 是 NP 完全的)或某种算法可以给出大致正确的结果。

请不要向我推荐“贪心算法”，因为我相信应该有一种算法可以给出更好的结果。我认为应该是一种使用“动态规划”的算法。

提前谢谢你:)

Answer 1

在这种特殊情况下，您可以通过最小化包中的可用空间并因此将重量作为一个值 来获得最大 yield 。此问题通常称为 subset sum problem并且是背包问题族的特例。

DP关系如下所示

在每个步骤中，您尝试在先前的元素集加上新元素中找到最大值(不超过袋子的容量)

子集求和问题的 C++ 实现，用于回答“我可以在给定这些元素的情况下完全填满袋子吗？”的问题。司机跟在后面

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

复杂度为 O(N⋅I)，其中 I 是起始集合中的元素数。这是一个伪多项式复杂度。

来源:Knapsack problem