I.cpp

#include <iostream>
#include <string.h>

using namespace std;

#define MAX_WEIGHT 50
#define MAX_PACKAGE 100

struct package{
    long toy;
    long weight;
};

int main(void){

    ios::sync_with_stdio(false);

    long T, N, final_weight;
    long matrix[MAX_PACKAGE+1][MAX_WEIGHT+1];
    long count_package[MAX_PACKAGE+1][MAX_WEIGHT+1];
    package list[MAX_PACKAGE];

    cin >> T;

    for(int k=0; k<T; k++){

        cin >> N;

        memset(matrix, 0, sizeof(matrix));
        memset(count_package, 0, sizeof(count_package));

        for(long i=0; i<N; i++){
            cin >> list[i].toy >> list[i].weight;
        }

        for(long i=1; i<=N; i++){
            for(long j=1; j<=MAX_WEIGHT; j++){

                if( list[i-1].weight <= j && matrix[i-1][j-list[i-1].weight] + list[i-1].toy >= matrix[i-1][j] ){

                    matrix[i][j] = matrix[i-1][j-list[i-1].weight] + list[i-1].toy;

                    if( matrix[i-1][j-list[i-1].weight] + list[i-1].toy == matrix[i-1][j] )
                        count_package[i][j] = min(count_package[i-1][j], count_package[i-1][j-list[i-1].weight] + 1);
                    else
                        count_package[i][j] = count_package[i-1][j-list[i-1].weight] + 1;

                }else{
                    matrix[i][j] = matrix[i-1][j];
                    count_package[i][j] = count_package[i-1][j];
                }
            }
        }

        for(final_weight=MAX_WEIGHT; final_weight&&matrix[N][final_weight]==matrix[N][final_weight-1]; final_weight--);

        cout << matrix[N][final_weight] << " brinquedos" << endl;
        cout << "Peso: " << final_weight << " kg" << endl;
        cout << "sobra(m) " << N - count_package[N][final_weight] << " pacote(s)" << endl << endl;
    }

    return 0;
}