wedding_shopping.md

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

 /*
  * 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;
 }