求助 dp问题 实在是想不出来

这应该是背包问题?

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

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

#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(超时) 这题最理想就是二分答案 代码我写在上面了 但是跟样例差点意思....