给定n个物品，每个物品有其价值和价格。要求你从中选择至少m个物品，最大化选择的物品的价值之和除以价格之和（即总的性价比）。

Input
第一行一个整数T(1 <= T <= 10)，表示数据组数。接下来T组数据：

对于每组数据，第一行两个整数n和m(1 <= m <= n <= 10000)，表示物品个数和需要选择的个数。

接下来n行，第i行两个整数Ai和Bi(1 <= Ai,Bi <= 1e8)，Ai表示第i个物品的价值，Bi表示第i个物品的价格。

Output
对于每组数据，输出一行，格式为："Case #K: ANS"，其中K表示当前是第K组数据。ANS表示最大的性价比，要求保留小数点后两位小数（"%.2f"格式输出即可）。

Sample Input
2

3 2

1000 10

1000 100

1 1

10 6

183 94

1626 3880

306 104

246 1408

969 1936

3456 1660

2161 192

1931 4821

15011 484

1205 25212

Sample Output
Case #1: 91.00

Case #2: 5.42

这应该是背包问题?

二分答案??

贪心+二分??
最大得选 考虑bi小的??

没看懂 他不是让求的sum价值/sum价格吗 不能用单一的来表示吧

您这样贪心明显不过样例吧

#include <stdio.h>
#include <math.h>
#define max(a,b) a<b?b:a
float a[10005];
float b[10005];
float c[10005];
void Swap(int *p, int *q)
{
    int buf;
    buf = *p;
    *p = *q;
    *q = buf;
    return;
}

void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high) //如果low >= high说明排序结束了
    {
        return ;
    }

    while (low < high) //该while循环结束一次表示比较了一轮
    {
        while (low < high && key <= a[high])
        {
            --high; //向前寻找
        }
        if (key > a[high])
        {
            Swap(&a[low], &a[high]);
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low; //向后寻找
        }
        if (key < a[low])
        {
            Swap(&a[low], &a[high]);
            --high;
        }
    }
    QuickSort(a, i, low-1); //用同样的方式对分出来的左边的部分进行同上的做法
    QuickSort(a, low+1, j); //用同样的方式对分出来的右边的部分进行同上的做法
}
int check(int mid,int n,int m)
{
    float sum = 0;
    for(int j = 1 ; j <= n ; j++)
    {
        c[j] = a[j] - mid*b[j];
    }
    QuickSort(c,c[1],c[n]);
    for(int j = 1 ; j <= m ; j++)
    {
        sum += c[j];
    }
    if(sum < 0)return 1;
    else return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int i = 1 ; i <= t ; i++)
    {
        int n,m;
        float r = -1,ans = 0;
        scanf("%d%d",&n,&m);
        for(int j = 1 ; j <= n ; j++)
        {
            scanf("%f%f",&a[j],&b[j]);
            r = max(a[j]/b[j],r);
        }
        printf("Case #%d: ",i);
        float l = 0,mid;
        while(r-l>0.001)
        {
            mid = (l+r)/2;
            if(check(mid,n,m))
            {
                l = mid;
            }
            else
            {
                r = mid;
            }
        }
        printf("%0.2f\n",mid);
    }
    return 0 ;
}

[此贴子已经被作者于2020-11-28 18:04编辑过]

这么大数据 动态规划肯定tle(超时) 这题最理想就是二分答案 代码我写在上面了 但是跟样例差点意思....