UVa 11450 - Wedding Shopping

Here I have used an adjacency list to v[i][j] which represents "i"th garment "j"th model value.
It can be solved using DP by defining two paramenters to be passed;:
1) "i"th index
2) "sum" obtained till "i"th index
Hence recurrence can be defines as:

for(j=0;j<v[i].size();j++)
    dp[i][sum]=max(dp[i][sum],solve(i+1,sum+v[i][j])).

which represents dp[i][sum]="0" if it is possible to reach value=sum till "i"th index else it would store negative value.

Base Case:
   when i==k && sum<=n --> ans=max(ans,sum)
                  that is on reaching "k"th element ans is the max sum obtained after considering all k values.
    when i>=k or sum>n  return -INF
                  as this value cannot be included in total as it exceeds the required value..

No Solution can be checked when included the lowest value of all "k" elements exceeds the required total value "n".

Top-Down Approach:

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,dp[30][500],k;

vi v[50];

int solve(int i,int sum){
    int j,z=0;
    if(i==k && sum<=n)
        return dp[i][sum]=0;
    if(i>=k || sum>n)
        return -1e5;
    if(dp[i][sum]!=-1)
        return dp[i][sum];
    f(j,0,v[i].size())
        z=max(z,solve(i+1,sum+v[i][j]));
    return dp[i][sum]=z;
}

int main(){
    int r,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        clr(dp,-1);
        c=0;
        sii(n,k);
        f(i,0,k){
            si(x);
            f(j,0,x){
                si(y);
                v[i].pb(y);
            }
        }
        f(i,0,k)
            sort(all(v[i]));
        z=0;
        f(i,0,k)
            z+=v[i][0];
        if(z>n)
            c=1;
        if(c)
            printf("no solution\n");
        else{
            solve(0,0);
            rf(i,300,0){
                if(dp[k][i]!=-1)
                    break;
            }
            pi(i);
        }
        f(i,0,k+5)
            v[i].clear();
    }
    return 0;
}