L4Q3

#include <iostream>
#include <cstdio>
#include <cstdio>

#define max(a,b) (a > b ? a : b)
using namespace std;


struct no
{
    int info;
    struct no *proximo;
};

class pilha
{
    struct no *topo;
public:
    pilha();
    void push(int);
    int pop();
    bool isVazia();
    void mostrar();
};

pilha::pilha()
{
    this->topo = NULL;
}

void pilha::push(int v)
{
    no *p = new no;
    p->info = v;
    p->proximo = NULL;
    if(topo!=NULL)
    {
        p->proximo = topo;
    }
    topo = p;
}

int pilha::pop()
{
    struct no *temp;
    int valor;
    if(topo!=NULL)
    {
        temp = topo;
        topo = topo->proximo;
        valor = temp->info;
        delete temp;
    }
    return valor;
}

bool pilha::isVazia()
{
    return (topo == NULL);
}

void pilha::mostrar()
{
    struct no *p = topo;
    if(topo!=NULL)
    {
        while(p!=NULL)
        {
            if (p->proximo != NULL)
            cout<<p->info<< " ";
            else
                cout<<p->info<< ".";
            p = p->proximo;
        }
    }
}


int matrix[10000][10000] = {0};
int escolhas[10000][10000] = {0};

//nItems = numero de items
//capMax = capacidade maxima da "mochila"
//os outros 2 arrays porque fica ruim de inserir bidimensional


int knapsack(int nItems, int capMax, int tempo[], int saudades[]){
    int i,j;

    for (i=1;i<=nItems;i++){
        for (j=0;j<=capMax;j++){
            if (tempo[i-1]<=j){
                matrix[i][j] = max(matrix[i-1][j],saudades[i-1]+matrix[i-1][j-tempo[i-1]]);
                if (saudades[i-1]+matrix[i-1][j-tempo[i-1]]>matrix[i-1][j])
                    escolhas[i][j]=1;
                else
                    escolhas[i][j]=-1;
            }
            else{
                escolhas[i][j] = -1;
                matrix[i][j] = matrix[i-1][j];
            }
        }
    }

    return matrix[nItems][capMax];

}

void imprimirEscolhas(int N, int capMax, int tempo[]){
      pilha p;
      int maximo = N-1;
      while (N > 0){
        if (escolhas[N][capMax]!=-1){
//            printf("Val: %d", N-1);
            p.push(N-1);
            N--;
            capMax -= tempo[N];
        }
        else{
            N--;
        }
    }
    p.mostrar();

    printf("\n");

return;
}

int main()
{
    freopen("L4Q3.in", "r", stdin);
    freopen("L4Q3.out", "w", stdout);

    int N; //amigos
    while (cin >> N)
    {
    if (N != 0)
    {
        string amigo;
        int* saudades = new int[N+1];
        int* tempo = new int[N+1];
        int T; //tempo
        cin >> T;

        for (int i = 0; i < N;i++){
            cin >> amigo;
            cin >> i;
            cin >> saudades[i] >> tempo[i];
//            cout << amigo << " " << i << " " << saudades[i] << " " << tempo[i] << endl;
        }

        knapsack(N, T, tempo, saudades);
        cout << "Amigos visitados: ";
        imprimirEscolhas(N,T, tempo);
//        cout<<(saudades,tempo,N,T)<<endl;


        }
    }
}