I wrote a different solution to Topcoder 647 DIV1 500 problem and can't understand why is it giving different (larger) results.

I brute force over all the sets of robots and then order each set increasingly by capacity. Then all robots travel together only so much that the robot with the least capacity can come back and compensate all the robots that have still not turned back, such that their capacity is again full. Once the robot has compensated all the others in full, it comes back and we apply the same logic to the robots left.

What is wrong with my logic?

Here is the code (note that it doesn't work for test cases larger than 31 in size):

class CtuRobots {
public:
    double brute(vector<double> &use) {
        sort(use.begin(), use.end());

        int n = use.size();
        vector<double> x(use.size(), 0);
        for(int i = 0; i < n; i++) {
            // subtract from the current capacity the way back
            // the rest is guaranteed to be non-negative
            double cur = use[i];
            for(int j = 0; j < i; j++)
                cur -= x[j];
            assert(cur >= 0.0);

            // split the left over capacity over the robots
            // that have still not turned back plus 2 times for the current
            // robot that has to go forward and then back
            cur /= (n-i+1);
            x[i] = cur;
        }

        // the answer is the sum of all the segments
        double ans = 0;
        for(int i = 0; i < x.size(); i++)
            ans += x[i];

        // check that we actually use all the fuel
        double chk = 0, sum = 0;
        for(int i = 0; i < x.size(); i++) {
            chk += (use.size()-i)*x[i];
            sum += use[i];
        }
        assert(abs(2*chk-sum) < 1e-9);

        return ans;
    }

    double maxDist(int B, vector <int> cost, vector <int> cap) {
        // brute force solution
        assert(cost.size() < 32);
        double brt = 0;
        for(int i = 0; i < (1 << cost.size()); i++) {
            int cur = 0;
            vector<double> use;
            for(int j = 0; j < cost.size(); j++) {
                if(i & (1 << j)) {
                    cur += cost[j];
                    use.push_back(cap[j]);
                }
            }
            if(cur <= B) {
                brt = max(brt, brute(use));
            }
        }

        // dynamic programming solution
        for(int i = 0; i < cost.size(); i++) {
            for(int j = 0; j < i; j++) {
                if(cap[j] > cap[i]) {
                    swap(cap[i], cap[j]);
                    swap(cost[i], cost[j]);
                }
            }
        }

        double dp[111111];
        for(int i = 0; i <= B; i++)
            dp[i] = 0;

        for(int i = 0; i < cost.size(); i++) {
            for(int j = B-cost[i]; j >= 0; j--) {
                dp[j+cost[i]] = max(dp[j]/3.0+cap[i], dp[j+cost[i]]);
            }
        }

        double ans = 0;
        for(int i = 0; i <= B; i++) {
            ans = max(ans, dp[i]/2.0);
        }

        assert(abs(ans-brt) < 1e-9);
        assert(brt >= ans);
        return ans;
    }
};

int main( int argc, char* argv[] ) {
    {
        int costARRAY[] = {50,25};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        int capARRAY[] = {1,1};
        vector <int> cap( capARRAY, capARRAY+ARRSIZE(capARRAY) );
        CtuRobots theObject;
        eq(0, theObject.maxDist(100, cost, cap),0.6666666666666666);
    }
    {
        int costARRAY[] = {23,5,8,20,15};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        int capARRAY[] = {108,30,42,100,94};
        vector <int> cap( capARRAY, capARRAY+ARRSIZE(capARRAY) );
        CtuRobots theObject;
        eq(1, theObject.maxDist(25, cost, cap),55.0);
    }
    {
        int costARRAY[] = {0,0,0,1000,1000,0,1000,0};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        int capARRAY[] = {2039,4819,5923,1577,8749,9182,3652,4918};
        vector <int> cap( capARRAY, capARRAY+ARRSIZE(capARRAY) );
        CtuRobots theObject;
        eq(2, theObject.maxDist(1382, cost, cap),6503.238683127572);
    }
    {
        int costARRAY[] = {185,130,109,1,45,117,127,13,2,37,6,1,2};
        vector <int> cost( costARRAY, costARRAY+ARRSIZE(costARRAY) );
        int capARRAY[] = {93,5,278,4,20,54,93,213,103,5,225,32,5};
        vector <int> cap( capARRAY, capARRAY+ARRSIZE(capARRAY) );
        CtuRobots theObject;
        eq(3, theObject.maxDist(209, cost, cap),190.48376771833563);
    }
    return 0;
}