来自 Coursera 的算法工具箱类(class)。
问题介绍
你得到一套金条,你的目标是尽可能多地把金条放进去
你的包。每个栏只有一个拷贝,对于每个栏,您可以接受或不接受
(因此你不能拿一小部分酒吧)。
问题描述
任务。给定 𝑛 金条,找出装进一袋容量 𝑊 的最大黄金重量。
输入格式。输入的第一行包含一个背包的容量 𝑊 和金条的数量 𝑛。下一行包含 𝑛 整数 𝑤0,𝑤1, 。 . . ,𝑤𝑛−1 定义金条的重量。
约束。 1 ≤ 𝑊 ≤ 10^4; 1≤𝑛≤300; 0 ≤ 𝑤0, . . . , 𝑤𝑛−1 ≤ 10^5。
输出格式。输出适合容量 𝑊 的背包的最大黄金重量。
我在 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;
}
最佳答案
计算很好,但是最大权重是 10000,而你的矩阵只上升到 1001,所以你得到了缓冲区溢出。
首先在堆栈上分配矩阵并不好,当你解决这个问题时情况会更糟。
此外,您实际上并不需要二维矩阵来解决此问题。
尝试维护可访问权重的排序列表。从 [0] 开始并为每个项目添加新的可访问权重。
关于c++ - 没有重复的背包 : Maximum Amount of Gold,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59444857/