Вариация ранца на соревнованиях по программированию

Вопрос:

Экзамен состоит из N вопросов. Оценки N вопросов: m1, m2, m3, .. mN соответственно. Джем сдает экзамен и хочет получить максимальное количество оценок. Однако ему требуется некоторое время, чтобы решить каждый вопрос. Время, затрачиваемое им на решение вопросов, равно t1, t2, t3, .. tN соответственно. Экзамены длятся в общей сложности T. Но учительница Джем очень умна и знает, что Джем найдет способ получить максимальные оценки. Итак, чтобы сбить Джема с толку, она также предлагает ему бонусное предложение. Предложение состоит в том, что Джем может выбрать вопрос, за который он может удвоить оценки, полученные за этот вопрос. Теперь Джем действительно сбит с толку. Помогите ему узнать максимальное количество баллов, которое он может набрать.

Ограничения

1<=N<=1000

1<=T<=10000

1<=mi<=100000

1<=ti<=10000

Я попробовал этот вопрос здесь и придумал следующий алгоритм:

Поскольку задача гласит, мы можем выбрать вопрос, за который он может удвоить баллы, полученные за этот вопрос.

Итак, для выбора этого вопроса я применил жадный подход, т.е.

1. следует выбрать вопрос с большим соотношением (баллы/время), за который он может удвоить баллы, присуждаемые за этот вопрос.

2. И если это соотношение тоже такое же, то следует выбирать вопрос с большей оценкой.

   А в остальном просто ранец насколько я понял вопрос. Я попробовал следующую реализацию, но получил неправильный ответ. для данного тестового примера мой код дает правильный вывод

   3 10 1 2 3 4 3 4

я пробовал этот тестовый пример, указанный в разделе комментариев, и мой код дает 16 в качестве вывода, но ответ должен быть 18

  3 
  9
  9 6 5
  8 5 3

Подход грубой силы приведет к превышению ограничения по времени, поскольку решение N рюкзаков сложности O (nW) даст общую временную сложность O (n ^ 2 W). Я думаю, что для этого вопроса может быть разработан более конкретный алгоритм. У кого-нибудь есть идея получше, чем эта?

Спасибо

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int T[2][10002];
    int a[1000002],b[100002];
    float c[100002];
    int knapSack(int W,int val[],int wgt[],int n)
    {
    int i,j;

    for(i=0;i<n+1;i++)
    {
        if(i%2==0)
        {
            for(j=0;j<W+1;j++)
            {
            if(i==0 || j==0)
            T[0][j]=0;
            else if(wgt[i-1]<=j)
            T[0][j]=max(val[i-1]+T[1][j-wgt[i-1]],T[1][j]);
            else
            T[0][j]=T[1][j];
            }
        }
        else
        {
            for(j=0;j<W+1;j++)
            {
            if(i==0 || j==0)
            T[1][j]=0;
            else if(wgt[i-1]<=j)
            T[1][j]=max(val[i-1]+T[0][j-wgt[i-1]],T[0][j]);
            else
            T[1][j]=T[0][j];
            }
        }
    }
    if(n%2!=0)
        return T[1][W];
    else
        return T[0][W];
    }


    int main()
    {
    int n,i,j,index,t,mintime,maxval;
    float maxr;
    cin>>n;
    cin>>t;
    for(i=0;i<n;i++)
        cin>>a[i];

    for(i=0;i<n;i++)
        cin>>b[i];

    maxr=0;
    index=0;
    mintime=b[0];
    maxval=a[0];

    for(i=0;i<n;i++)
        {
            c[i]=(float)a[i]/b[i];  
                if(c[i]==maxr && b[i]<=t)
                {
                    if(a[i]>=maxval)
                    {
                    maxval=a[i];
                    mintime=b[i];
                    index=i;
                    }
                }   
                else if(c[i]>maxr && b[i]<=t)
                {
                maxr=c[i];
                maxval=a[i];
                mintime=b[i];
                index=i;
                }

        }

    a[index]=a[index]*2;
    int xx=knapSack(t,a,b,n);
    printf("%d\n",xx);
    }