c++ - 只有重量的背包

Question

如果我给了最大重量说 w=20 并且我给了一组重量说 m=[5,7,12,18] 那么我怎么能计算出我们可以容纳的最大可能重量使用 m 的最大重量。在这种情况下，答案是 19。通过添加 12+7=19。我的代码给了我 18。请帮助我。

int weight(int W, vector<int> &m) {

  int current_weight = 0;
  int temp;
  for (int i = 0; i < w.size(); i++) {
    for (int j = i + 1; j < m.size(); j++) {
      if (m[i] < m[j]) {
        temp = m[j];
        m[j] = m[i];
        m[i] = temp;
        }
      }
    }

  for (size_t i = 0; i < m.size(); ++i) {
    if (current_weight + m[i] <= W) {
       current_weight += m[i];
      }
    }
 
  return current_weight;
  }

Answer 1

您描述的问题看起来更像是 maximum subset sum 的一个版本问题。基本上，首先您的实现没有任何问题；显然你已经正确地实现了这个问题的贪心算法。也就是说，该算法无法为每个输入生成最优解。你找到的实例就是这样的例子。

但是，可以使用称为 dynamic programming 的不同方法解决该问题。 ，这可以看作是解决方案的递归公式的组织形式。

设 m = { m_1, ... m_n } 是正项大小的集合，W 是一个容量约束，其中 n 是一个正整数。将数组 A[n][W] 组织为状态空间，其中<​​/p>

A[i][j] = the maximum weight at most j attainable for the set of items
          with indices from 0 to i if such a solution exists and 
          minus infinity otherwise

对于每个 i in {1,...,n} 和 j in {1,...,W}；为了便于演示，假设 A 在其他任何地方都具有负无穷大的值。请注意，对于每个这样的 i 和 j 递归关系

A[i][j] = min { A[i-1][W-m_j] + m_j, A[i-1][W] }

成立，第一种情况对应于选择项目 i 进入解决方案，第二种情况对应于不选择项目 i 进入解决方案解决方案。

接下来，组织一个循环，按照 i 和 j 值递增的顺序填充此表，其中 i = 1 的初始化> 必须在之前完成。填充状态空间后，最后一列的最大可行值

max{ A[n][j] : j in {1,...,W}, A[n][j] is not minus infinity }

产生最优解。如果还需要关联的项目集，则必须使用一些回溯或合适的辅助数据结构。