# UVa 11450

## Summary

Given a money M (<= 200) and a list of garments C (<= 20). Each garment has K (<= 20) models. You want to buy one model for each garment and you want to spend your money as much as possible.

## Explanation

This is a typical Dynamic Programming problem. Let dp(m,c) be the maximum money you can spend when you have m money and you want to buy one model for each garment from garment 0 to garment c-1. If it's not possible to buy one model for each garment then the value of dp(m,c) is -2 (or any other special value).

Then dp(m,c) can be computed recursively:

```dp(m,c) =        -2,   if m is negative
c,   if c is zero
max(spending),   otherwise
```

Where spending is the maximum value of dp(m-ci, c-1) + ci for all the prices of model ci of garment c-1 and dp(m-ci, c-1) is not -2.

The total complexity is O(M*C*max(K)) which is around 200*20*20 = 80,000 operations per test case.

## Implementations

Dynamic Programming can be implemented in a top-down manner or a bottom-up manner.

• Below is the top-down version (recursion model):
```#include <stdio.h>
#include <vector>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

vector<int> G;
int dp;

if (m<0) return -2;      // negative money means no solution
if (c==0) return 0;      // no more garment to buy, this is a solution
int &ret = dp[m][c];     // ret is an alias of dp[m][c]
if (ret!=-1) return ret; // if the current state is already visited, return immediately
ret = -2;                // initialize this state as having no solution (-2)
REP(i,G[c-1].size()){    // for all model of this garment
int ci = G[c-1][i];             // the price of model ci of garment c-1
if (buy(m-ci, c-1) != -2)       // if this model can produce a solution
ret >?= buy(m-ci, c-1) + ci;  // update the maximum money spent
}
return ret;
}

int main(){
int N,M,C,K;
scanf("%d",&N);
while (N--){
scanf("%d %d",&M,&C);
REP(i,C){
scanf("%d",&K);
G[i].resize(K);                        // resize the vector to size K
REP(j,K) scanf("%d",&G[i][j]);
}
memset(dp,-1,sizeof(dp));
if (buy(M,C) == -2) puts("no solution"); // -2 means no solution
else printf("%d\n", buy(M,C));           // this will return the memoized solution
}
}
```
• Below is the bottom-up version:
```#include <stdio.h>
#include <vector>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)
#define FOR(i,a,b) for (int i=a,_n=b; i<=_n; i++)

vector<int> G;
int dp;

int main(){
int N,M,C,K;
scanf("%d",&N);
while (N--){
scanf("%d %d",&M,&C);
REP(i,C){
scanf("%d",&K);
G[i].resize(K);                        // resize the vector to size K
REP(j,K) scanf("%d",&G[i][j]);
}

FOR(m,0,M) FOR(c,0,C) dp[m][c] = -2;     // initialize this state as having no solution (-2)

FOR(m,0,M){
dp[m] = 0;                          // base case solution
FOR(c,1,C){
REP(i,G[c-1].size()){
int ci = G[c-1][i];                // the price of model ci of garment c-1
if (m>=ci && dp[m-ci][c-1]!=-2)    // if this model can produce a solution
dp[m][c] >?= dp[m-ci][c-1] + ci; // update the maximum money spent
}
}
}
if (dp[M][C] == -2) puts("no solution");
else printf("%d\n", dp[M][C]);
}
}
```