我对背包问题有一个变体,我正在努力寻找有效的解决方案。
假设您有多组项目。每个组可以有任意数量的物品,每个物品都有一个值和重量。问题是找到总价值最大、重量
也就是说,想象一下你有数百种物品可供选择,但你必须带一份三明治、一份饮料、一份零食、一只手电筒等。不仅你不能从任何一组中拿走多于一件,而且你必须至少拿走一件。如果有 g 个组,那么一天结束时总共会得到 g 个项目。
看起来这应该比基本问题更快,因为很多组合都是无效的,但我正在努力寻找解决方案。
C++ 中的示例代码。该函数返回可实现的最大值,或者-1
如果不存在可行的解决方案。它运行在O(n * max_weight)
where n
是计算所有组的项目总数,并且max_weight
是重量限制。其复杂度本质上与解决原始背包问题的经典算法相同。该代码实现了 Evgeny Kluev 答案中的算法。
int CalcMaxValue(const std::vector<std::vector<int>>& weight,
const std::vector<std::vector<int>>& value,
int max_weight) {
std::vector<int> last(max_weight + 1, -1);
if (weight.empty()) return 0;
for (int i = 0; i < weight[0].size(); ++i) {
if (weight[0][i] > max_weight) continue;
last[weight[0][i]] = std::max(last[weight[0][i]], value[0][i]);
}
std::vector<int> current(max_weight + 1);
for (int i = 1; i < weight.size(); ++i) {
std::fill(current.begin(), current.end(), -1);
for (int j = 0; j < weight[i].size(); ++j) {
for (int k = weight[i][j]; k <= max_weight; ++k) {
if (last[k - weight[i][j]] < 0) continue;
current[k] = std::max(current[k], last[k - weight[i][j]] + value[i][j]);
}
}
std::swap(current, last);
}
return *std::max_element(last.begin(), last.end());
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)