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

Question

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

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

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

请不要推荐我"greedy algorithms"，因为我相信应该有一个算法可以给出更好的结果。我认为它应该是一种使用 "dynamic programming".

的算法

提前谢谢你:)

Answer 1

描述的问题其实不是0-1-Knapsack problem, but a special case thereof, also called the Maximum Subset Sum problem, which is desribed here。它是 NP-complete，这意味着它并不比 0-1-Knapsack 复杂性更容易。

话虽这么说，它可以通过将项目利润设置为等于它们的权重来通过任何旨在解决 0-1-Knapsack 问题的优化算法来解决。总的来说，可以使用以下动态规划算法将其求解为最优； s[i] 表示第 i 项和 m 是整数值状态 space 时的大小，其中 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

Answer 2

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

DP关系如下所示

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

子集和问题的 C++ 实现来回答问题 "can I fill the bag entirely given these elements?" 和驱动程序如下

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

Answer 3

看起来像Spoj problem。我的解决方案是：

#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]，将sum(Wi, Wj)，foreach k 并找到MAX sum(Wi, Wj) + Wk.

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

Algorithm for Filling bag maximally (this is not the knapsack 0/1)

algorithm

pseudocode

dynamic-programming