最大化装满袋子的算法（不是0/1背包问题）

Question

我正在处理一个任务，需要我解决以下算法问题：

---

- 你有一系列物品（它们的重量）：[w1, w2, ..., wn]
- 你有一个袋子，它的重量为W
- 需要用给定的物品子集尽可能地填满袋子。

---

因此，这不是“0/1背包”问题，因为我们只涉及重量（每个物品只有一个参数）。因此，我认为可能有一种解决方案（背包问题是NP完全问题）或某种能够提供近似正确结果的算法。

请不要建议我使用“贪心算法”，因为我相信应该有一种可以得到更好结果的算法。我认为它应该是一种使用“动态规划”的算法。

提前感谢你的帮助 :)

- haykart

---

结果证明，这确实是0/1背包问题，只需将价格设置为与重量相同即可。 - harold

从那个角度来看，你是正确的，但我认为对于这个问题可能有一个解决方案，因此我将其命名为“非背包” :) - haykart

Answer 1

事实上，所描述的问题并不是0-1背包问题，而是它的一个特殊情况，也称为最大子集和问题，该问题在此处有描述。它是NP完全问题，这意味着从复杂度角度来看，它并不比0-1背包问题更容易。

话虽如此，通过将物品利润设置为它们的重量，可以使用任何旨在解决0-1背包问题的优化算法来解决它。总体而言，可以使用以下动态规划算法完美地解决它；s[i]表示第 i 个物品的大小，而m是一个整数值状态空间，其中m[i,s]表示使用物品范围{0,...i}中的物品可以达到的最大值。

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if s[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-s[i]] + s[i])

正如原问题中提到的，以下贪心算法是对背包问题相似算法的修改，可以得到2近似解。

1. select any subset of the items such that there is no other
   item which can be feasibly chosen
2. select the largest item
3. out of 1. and 2., choose the subset which yields the larger total size

- Codor

Answer 2

在这种情况下，通过最小化袋子中的自由空间并将重量视为价值来获得最大效益。这个问题通常被称为子集和问题，是背包问题家族的一个特例。

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是起始集合中元素的数量。这是一个伪多项式复杂度。

来源：背包问题

- Marco A.

---

谢谢您的解释，但我不想完全填满袋子，我只想知道我可以用多少重量来填充袋子，也许我没有完全理解，但我认为您提出的算法不能解决我的问题。 - haykart

@haykart，正如我之前所写的算法一样，它回答了这个问题：“我能把袋子装满吗？”。修改算法以回答这个问题：“我可以用这些元素填充袋子的最大尺寸是多少？”是微不足道的：只需输出值m[I][N]，您就可以知道您的袋子可以填充到的最大值。 - Marco A.

Answer 3

它看起来像Spoj问题，我解决的方法是：

#include <bits/stdc++.h>

using namespace std;

int TimTongLonNhatCoGioiHan(int*arr, int songuoichoi, int gioihan){

  int hmm = (int)(songuoichoi*songuoichoi/2);
  int map[hmm];

  int dem = 0, i, j, ox = songuoichoi - 1, oy = 0, result = 0, sum;
  for(i = ox; i > oy; --i){
    for(j = oy; j < ox; ++j){
      map[dem] = arr[i] + arr[j];

      // tinh tong lon nhat cua 3 so
      for(int k = 0; k < songuoichoi; ++k){
        if(k == j || k == i)
          continue;
        sum = map[dem] + arr[k];
        if(sum > result && sum <= gioihan)
          result = sum;
      }
      dem++;
    }
    -- ox;
  }

  return result;
}

int main() {
  int sophantu = 0, songuoichoi = 0, gioihan = 0;
  cin>>sophantu;
  while(sophantu-->0){
    cin>>songuoichoi;
    int i = 0;
    int arrCanNang[songuoichoi];
    for(; i<songuoichoi; ++i){
      cin>>arrCanNang[i];
    }
    cin>>gioihan;

    cout<<TimTongLonNhatCoGioiHan(arrCanNang, songuoichoi, gioihan)<<"\n";
  }
  return 0;
}

简单来说，您可以创建一个矩阵 [w1, w2, ..., wn] x [w1, w2, ..., wn]，计算每个 Wi 和 Wj 的和，并找到 MAX sum(Wi, Wj) + Wk。

- Khai Vu