11450 - Wedding shopping
- Problem require us to find the maximum amount of dresses(have multiple brands) in given amount of money.
- Kind of 0-1 Knapsack
- States are,
money and index_of_brands
Code sample
```cpp
/*
* price being the 2d-array storing data
* memo being 2d-array used for memoization.
*/
int ourFunction(CurrentMoney, index) {
if (CurrentMoney < 0)
return -INF; /* INF, being very large values. */
if (index == TotalBrands)
return TotalMoney - CurrentMoney;
int &ans = memo[money][g];
if (ans != -1)
return ans;
/* Loop isnt the part of the template, loop is just to access data from the given 2d data,
* if data were 1d then we would have gone without loop
*/
for (int brand = 1; brand <= price[index][0]; brand++) /* at index,0 we have stored the size of that specific brand. */
ans = max(ans, ourFunction(CurrentMoney - price[index][CurrentMoney], index + 1));
return ans;
}
```