不带背包的背包：最大数量的黄金

Question

摘自Coursera的Algorithmic Toolbox课程。

问题介绍

您获得了一组金条，而您的目标是将尽可能多的金放入你的包。每个酒吧只有一个副本，您可以选择是否接受每个酒吧（因此，您不能花费一小部分）。

问题描述

任务。给定𝑛个金条，找到适合容量𝑊袋的最大黄金重量。输入格式。输入的第一行包含背包的容量and和金条的数量𝑛。下一行包含𝑛个整数𝑤0，𝑤1，。 。 。 ，𝑤𝑛−1定义了金条的权重。

约束。 1≤𝑊≤10 ^ 4; 1≤𝑛≤300; 0≤𝑤0，。 。 。 ，𝑤𝑛−1≤10 ^ 5。

输出格式。输出适合容量为na的背包的最大重量黄金。

我在C ++中的解决方案：

const int WEIGHT_MAX = 1000 + 1;
const int ITEMS_COUNT_MAX = 300 + 1;

int optimal_weight(int W, const vector<int> &w) {
  int weights[ITEMS_COUNT_MAX][WEIGHT_MAX];
  const int w_size = w.size();

  for (int i = 0; i <= w_size; i++) {
    for (int j = 0; j <= W; j++) {      
        if (i==0 || j==0) 
          weights[i][j] = 0;
        else if (w[i - 1] <= j) 
          weights[i][j] = std::max(w[i - 1] + weights[i - 1][j - w[i - 1]],  weights[i - 1][j]);
        else
          weights[i][j] = weights[i - 1][j];
    }
  }

  int result = weights[w_size][W];
  return result;
}

用于输入

10 3
1 4 8

...它产生以下二维矩阵：

0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 4 5 5 5 5 5 5
0 1 1 1 4 5 5 5 8 9 9

但是14位学生的测验中没有9分通过。分级机不提供使用的输入。

有人可以指出解决方案中的警告吗？

更新[已解决，感谢Matt]：必须在堆上分配内存，因为本地堆栈大小不足以容纳大小为10001х301的数组。实际上，尝试在堆栈上分配时出现分段错误错误。

int optimal_weight(int W, const vector<int> &w) {
  const int w_size = w.size();
  int** weights = new int* [w_size + 1];

  for (int i = 0; i <= w_size; i++) {
    weights[i] = new int[W + 1];
  }

  for (int i = 0; i <= w_size; i++) {
    for (int j = 0; j <= W; j++) {      
        if (i==0 || j==0) {
          weights[i][j] = 0;
        }
        else if (w[i - 1] <= j) 
          weights[i][j] = std::max(w[i - 1] + weights[i - 1][j - w[i - 1]],  weights[i - 1][j]);
        else
          weights[i][j] = weights[i - 1][j];
    }
  }

  int result = weights[w_size][W];

  for (int i = 0; i < w_size; i++) {
    delete[] weights[i];
  }

  delete[] weights;

  return result;
}

Answer 1

该计算很好，但是最大权重为10000，并且矩阵仅增加到1001，因此您将出现缓冲区溢出。

首先在堆栈中分配矩阵并不好，而解决该问题会更加糟糕。

而且您实际上并不需要二维矩阵来解决此问题。

尝试维护可访问权重的排序列表。从[0]开始，然后为每个项目添加新可访问的权重。