正确的写法：
void solve()
{
    double left = 0.0;
    double right = 0.0;
    for (int i = 0; i < N; i++)
        right = max(right, 1.0 * value[i] / weight[i]);

    while (1)
    {
        double mid = (left + right) / 2.0;
        for (int i = 0; i < N; i++)
        {
            item[i].idx = i + 1;
            item[i].prior = value[i] - mid * weight[i];
        }
        sort(item, item + N);

        double sum = 0.0;
        for (int i = 0; i < K; i++)
            sum += item[N - K + i].prior;

        if (sum >= 0.0)
        {
            left = mid;
            if (right - left < 1e-7)
                break; //跳出二分时需要保证运行结果是可行解
        }
        else
            right = mid;
    }

    sort(item + N - K, item + N, cmpIdx);

    for (int i = 0; i < K; i++)
        printf("%d ", item[N - K + i].idx);
}

错误的写法：
（跳出二分时，item数组中存储的可能不是可行解）
void solve()
{
    double left = 0.0;
    double right = 0.0;
    for (int i = 0; i < N; i++)
        right = max(right, 1.0 * value[i] / weight[i]);

    while (right - left >= 1e-7)
    {
        double mid = (left + right) / 2.0;
        for (int i = 0; i < N; i++)
        {
            item[i].idx = i + 1;
            item[i].prior = value[i] - mid * weight[i];
        }
        sort(item, item + N);

        double sum = 0.0;
        for (int i = 0; i < K; i++)
            sum += item[N - K + i].prior;

        if (sum >= 0.0)
            left = mid;
        else
            right = mid;
    }

    sort(item + N - K, item + N, cmpIdx);

    for (int i = 0; i < K; i++)
        printf("%d ", item[N - K + i].idx);
}

• 哪位大佬帮看下我的代码哪里有问题。。。实在找不到了。。 (898) 1540873272 2018-05-17 12:22:41
  • Re:哪位大佬帮看下我的代码哪里有问题。。。实在找不到了。。 (1053) wangpeiyi9979 2019-05-25 00:25:21