装载问题

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++;
        }
    }
}