Dynamic Programming: From novice to advanced

/*
  Name: 2008. Dab of Backpack
  Copyright: Tiger
  Author: LDT
  Date: 02/12/08 02:46
  Description:
    - http://www.spoj.pl/problems/BACKPACK/
*/
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

const int maxn  = 100;
const int maxV  = 3210;

int n;
int v[maxn];
int c[maxn];
int phu[maxn];
int tich[maxn];
int dsphu[maxn][3];
int nphu[maxn];
int vMax;
int ll[maxn][maxV];
ifstream fi("input.txt");

void readf(){
    cin >>vMax >> n ;
    vMax /= 10;

    //cout <<" n = " <<n <<" vMax = " <<vMax <<endl;
    for (int i=1; i<=n; i++)
    {
        cin >> v[i] >>c[i] >>phu[i];
        tich[i] = v[i]*c[i];
        v[i] /= 10;
    }

}

void init(){
    for (int i = 1; i<=n; i++)
    {
        if (phu[i] > 0)
        {
            int p = phu[i];
            dsphu[p][nphu[p]] = i;
            nphu[p]++;
              //cout <<" i = " <<i <<" phu[i] = " <<phu[i] <<" nphu[p] = " <<nphu[p] <<" dsphu[p][nphu[p]] = "
            //    <<dsphu[p][nphu[p]-1]  <<endl;
        }                 
    }

}

int Max(int a ,int b){
    if (a > b)
        return a;
    else
        return b;
}

void solve()
{
    //cout <<"solve" <<endl;
    for (int i = 1; i<=n; i++)
    {
        ll[i][0] = 0;
    }
    for (int i = 1; i<=vMax; i++)
    {
        ll[0][i] = 0;
    }

    //cout <<"loop" <<endl;

    for (int j = 1; j<=vMax; j++)
    {
        for (int i = 1; i<=n; i++)
        {
            ll[i][j] = ll[i-1][j];
            if ((v[i] <= j) && (phu[i] == 0))
            {
                //NOTE: Moi mon hang lay 1 lan

                // khong lay phu
                int layi = v[i]*c[i]*10;
                ll[i][j] = Max(ll[i][j],ll[i-1][j-v[i]]+tich[i]);

                if (nphu[i] == 1){
                    //lay phu 1 mon hang
                    int csphu1 = dsphu[i][0];
                    int lay1 = v[csphu1]*c[csphu1]*10;
                    if (v[i]+v[csphu1] <= j)
                        ll[i][j] = Max(ll[i][j],ll[i-1][j-v[i]-v[csphu1]] + tich[i] + tich[csphu1]);
                }

                if (nphu[i] == 2){
                    int csphu1 = dsphu[i][0];
                    int csphu2 = dsphu[i][1];

                    //lay phu 1 mon hang
                    if (v[i]+v[csphu1] <= j)
                        ll[i][j] = Max(ll[i][j],ll[i-1][j-v[i]-v[csphu1]] + tich[i] + tich[csphu1]);
                    if (v[i]+v[csphu2] <= j)
                        ll[i][j] = Max(ll[i][j],ll[i-1][j-v[i]-v[csphu2]] + tich[i] + tich[csphu2]);

                    //lay ca 2 mon hang phu
                    if (v[i]+v[csphu1] + v[csphu2] <= j)
                        ll[i][j] = Max(ll[i][j],ll[i-1][j-v[i]-v[csphu1]-v[csphu2]] + tich[i] + tich[csphu1] + tich[csphu2]);
                }

            }
        }
    }
}

int main()
{
    int sotest;
    cin >> sotest;
    for (int i = 1; i<=sotest; i++)
    {
        //cout<<"* test " <<i <<endl;
        memset(ll,0,sizeof(ll));
        memset(dsphu,0,sizeof(dsphu));
        memset(nphu,0,sizeof(nphu));
        memset(v,0,sizeof(v));
        memset(c,0,sizeof(c));
        memset(phu,0,sizeof(phu));
        memset(tich,0,sizeof(tich));
        readf();
        init();
        solve();
        cout <<ll[n][vMax] <<endl;
    }
    return EXIT_SUCCESS;
}