背包仅含重量

Question

如果我给出了最大重量，比如 w=20 。并且我给出了一组权重，比如 m=[5,7,12,18] 那么我如何计算我们可以在最大重量内保持的最大可能重量他们。在本例中，答案是 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

您描述的问题看起来更像是最大子集和问题的一个版本。基本上，您的实施一开始就没有任何问题；显然你已经正确地实现了该问题的贪婪算法。话虽如此，该算法无法为每个输入生成最佳解决方案。您找到的实例就是这样的一个例子。

但是，可以使用称为动态规划的不同方法来解决该问题，该方法可以视为解决方案的递归公式的组织形式。

让为正项目大小和容量约束的m = { m_1, ... m_n }集合，其中是正整数。将数组组织为状态空间，其中WnA[n][W]

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 }

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