Ralph And Code-Sigma

This problem was a very straight forward one. There was no tricky part at all. Simply the contestants were to use any efficient algorithm for 0/1 KnapSack problem. 

The purpose behind this problem was to make newbies search the net and find out more about the 0/1 KnapSack problem and it's variants. The best way of solving this problem during a contest is to use Dynamic Programming techniques.

Here is the master Solution in C++:

#include <cstdio>
using namespace std;

class problem 
{
    private:
        int N,H,n;
        long AVG;
        int DIF[550];
        int TIM[550];
        int RAT[550];
        int dp [550][330];
        
        inline void print()
        {
            int rating = AVG/10;
            if ( AVG == 0 )
            {
                printf("FIASCO\n");
                return;
            }
            rating++;
            if ( rating == 11 )
            {
                printf("OUT OF BOX\n");
                return;
            }
            printf("%d\n",rating);
        }
            
    public:
        explicit problem()
        {
            int D,R,T;
            n=0;
            AVG=0;
            scanf("%d %d",&N,&H);
            for(int i=1;i<=N;i++)
            {
                scanf("%d %d %d",&D, &R, &T );
                DIF[i]=D;
                RAT[i]=R;
                TIM[i]=T;
            }
            for(int i=0; i<=H; i++ ) dp[0][H] = 0;
            for( int i=1; i<=N; i++)
                for( int j=0; j<=H; j++)
                {
                    if ( j>= TIM[i] )
                    {
                        if (dp[i-1][j-TIM[i]]+DIF[i] > dp[i-1][j] )
                        {
                            AVG += RAT[i];
                            n++;
                            dp[i][j] = dp[i-1][j-TIM[i]]+DIF[i];
                        }
                        else dp[i][j] = dp[i-1][j];
                    }
                    else dp[i][j] = dp[i-1][j];
                }
            AVG/=n;
            print();
        }
};

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) problem p = problem();
    return 0;

} 


Here is the link to the wikipedia page of 0/1 KnapSack Problem  http://en.wikipedia.org/wiki/Knapsack_problem