装载问题
template<class T>
T MaxLoading(std::vector<T>& w, T c, int n, std::vector<int>& bestx) {
int i = 1;
std::vector<int> x(n + 1);
T bestw = 0, cw = 0, r = 0;
for (int j = 1; j <= n; j++) {
r += w[j];
}
while (true) {
while (i <= n && cw + w[i] <= c) {
r -= w[i];
cw += w[i];
x[i] = 1;
i++;
}
if (i > n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
bestw = cw;
}
}
else {
r -= w[i];
x[i] = 0;
i++;
}
while (cw + r <= bestw) {
i--;
while (i > 0 && !x[i]) {
r += w[i];
i--;
}
if (i == 0) {
return bestw;
}
x[i] = 0;
cw -= w[i];
i++;
}
}
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 16:56:10
创建日期: 2024年1月2日 16:56:10