Fibonaccibug 10/100

I pochi risultati che non vanno fuori tempo risultano corretti, se qualcuno potrebbe aiutarmi ad ottimizzare il codice sottostante ne sarei grato.

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>

#define MAXN 100000
using namespace std;

struct offer
{
    int grade;
    long long ants;
    int price;
    float ppa;
};

long long antnum(int n)
{
    if((n==0)||(n==1))
        return 1;
    else{
        return antnum(n-1)+antnum(n-2);
    }
}

bool comp(offer a, offer b)
{
    return a.ppa>=b.ppa;
}

int T, N, K, i, j;
int A[MAXN], B[MAXN];
long long ris=0;
vector<offer> vett;

int main() {
  //freopen("input0.txt", "r", stdin);
  //freopen("output0.txt", "w", stdout);

    assert(1 == scanf("%d", &T));
    for(i=0; i<T; i++) {

        assert(2 == scanf("%d %d", &N, &K));

        vett.resize(N);

        for (j=0; j<N; j++)
        {
            assert(2 == scanf("%d %d", &A[j], &B[j]));
            vett[j].grade=A[j];
            vett[j].price=B[j];
            vett[j].ants=antnum(A[j]);
            vett[j].ppa=vett[j].price/vett[j].ants;
        }
        j=0;
        sort(vett.begin(), vett.end(), comp);
        while(j<vett.size())
        {
            if(K-vett[j].ants>=0)
            {
                ris=ris+vett[j].price;
                K=K-vett[j].ants;
            }

            else j++;
        }
        printf("%lld\n", ris);
        ris=0;
        vett.clear();
    }
    return 0;
}

Ho creato un vettore dinamico di strutture “offer” contenenti ognuna grado della colonia, valore, numero di formiche e valore per formica. Lo ordino poi in base al valore per formica e controllo dalla prima offerta (migliore) se può essere comprata: in tal caso aggiorno il risultato, se no vado alla prossima offerta.
Grazie in anticipo.

Salve, la funzione di fibonacci ha come complessitĂ  O(2^N). ComplessitĂ  troppo alta per valori che raggiungono 10^5.
Con il seguente caso di test la tua soluzione va fuori tempo massimo:

1
5 11
1 2
2 2
3 5
4 9
100000 50

Un modo per ottimizzare il calcolo di fibonacci è di memorizzare i risultati intermedi attraverso la memoizzazione.

1 Mi Piace

E comunque la tua greedy non dovrebbe essere giusta, prova questo tc:

1
2 17
3 3
5 8

Scusa l’ignoranza, ma cos’è una greedy?

Qui Fibonacci serve solo per ridurre a poche decine il numero di colonie da prendere in considerazione.

Non ti preoccupare :slightly_smiling_face:
In parole povere ogni volta che in un algoritmo fai una scelta a priori escludendo le altre possibilità, nel tuo caso è prendere sempre la colonia con rapporto costo/numero maggiore tra tutte le possibili.
Ti lascio qualche esempio per chiarificare un po’.