How to approach this Dynamic Programming Meal Plan Problem?

Question

I came across this problem in a practice interview. I don't want a direct answer, just some help with the intuition of the problem, both your brute force thinking and how you would optimize that.

Method Signature:

int[] choosingShops(int cntProducts, int[][] quantities, int[][] costs, int[][] meals){}

Question is as follows:

You've created a meal plan for the next few days, and prepared a list of products that you'll need as ingredients for each day's meal. There are many shops around you that sell the products you're looking for, but you only have time to visit one or two stores each day.

Given the following information, your task is to find the minimum cost you'll need to spend on each meal:

• cntProducts - an integer representing the total number of products you'll be using in all of your meals;

• quantities - a rectangular matrix of integers, where quantities[i][j] represents the amount of product j available in shop i;

• costs - a rectangular matrix of integers, where costs[i][j] represents the cost of buying product j from shop i;

• meals - a rectangular matrix of integers, where meals[m][j] represents the amount of product j required to make the mth meal.

Return an array of length meals.length representing the minimum cost of each meal (assuming you can only visit up to two shops each day).

EXAMPLE

Inputs:

cntProducts = 2
quantities = [[1, 3], [2, 1], [1, 3]]
costs = [ [2, 4], [5, 2], [4, 1]]
meals = [ [1, 1], [2, 2], [3, 4]]

Answer:

choosingShops(cntProducts, quantitites, costs, meals) = [3, 8, 19].

Answer 1

int getprodmulti(int cost1, int cost2, int qty1, int qty2, int req){    
    if(cost1<=cost2){
        if(qty1>=req) return req*cost1;          
        return (qty1*cost1)+cost2*(req-qty1);
    }
    if(qty2>=req) return req*cost2;     
    return (qty2*cost2)+cost1*(req-qty2);
}
int getcostsMulti( vector<int> meal, vector<vector<int>> quantities, vector<vector<int>> costs){
    int min=INT_MAX,cost; 
    for(int i=0;i<costs.size()-1;i++){
        for(int j=i+1;j<costs.size();j++){
            cost=0;
            for(int k=0;k<meal.size();k++)    {
                if(quantities[i][k]+ quantities[j][k]<meal[k]) {
                    cost=0;
                    break;
                }
                int temp=getprodmulti(costs[i][k],costs[j][k],quantities[i][k],quantities[j][k],meal[k]);
                cost+=temp;
            } 
            if(min==-1) min=cost;                
            else if(cost!=0 && cost<min) min=cost;
        } 
    }
    return min;
}
vector<int> solution(int cntProducts, vector<vector<int>> quantities, vector<vector<int>> costs, vector<vector<int>> meals) {
    vector<int> res(meals.size());
    for(int i=0;i<meals.size();i++)     
            res[i]=getcostsMulti(meals[i],quantities,costs);        
        return res;
}

Answer 2

This solution is effectively calling the function cost(CNT_PRODUCTS, quantities, costs, meals[m] in parallel. The next meals is served on a new day.

One can brute-force this problem by considering all pairs of shops, and all single-shop visits. If the pairs of shops are equal, that is a single-shop visit. I have provided code snippets with trace.

1.1: Determining Satisfiability of pair

Let satisfiable(i, j, Q) represent the feasibility of the shops visited given Q. The pair i, j is satisfiable if for all products k, the quantities Q[i][k] + Q[j][k] >= meals[m][k]. We can save the Q[i][k] + Q[j][k] in a cubic array S of size O(SHOPS*SHOPS*CNT_PRODUCTS).

Calculating satisfiable(i, j, Q) for all pairs of shops (which will all be considered) can be done by looking up if S[i][j][k] >= meals[m][k] while looping through k.

    public static int choosingShops(final int CNT_PRODUCTS, int[][] Q, int[][] C, int[] X) {
        boolean satisfiable;
        int cost;
        int mincost = -1;
        
        // Search through all solos and pairs
        for (int i1 = 0; i1 < Q.length; i1++) {
            for (int i2 = i1; i2 < Q.length; i2++) {
                satisfiable = satisfiesQuantity(CNT_PRODUCTS, Q, X, i1, i2);
                if (satisfiable) {
                    System.out.printf("Shops #%d, #%d is feasible\n", i1, i2);
                    cost = cost(CNT_PRODUCTS, Q, C, X, i1, i2);
                    if (mincost == -1 || cost < mincost) {
                        mincost = cost;
                    }
                }
            }
        }
        return mincost;
    }

1.2: Calculating cost

Loop through all the pairs, considering only the satisfiable pairs.

For each satisfiable pair i, j, for each item k, we take as much as possible from the shop i1st which sells item k at a lower price, and if i1st does not supply all of the requirement, take meals[m][k] - Q[i1st][k] from i2nd to satisfy the requirement.

The cost is then calculated for shop i, j. Keep track of the minimum cost achieved so far. Then, the answer at index m is the smallest cost that is required to satisfy the particular meal meals[m] over satisfiable shops.

Calculating cost for each i, j is a linear O(CNT_PRODUCTS) time problem. There is a quadratic amount of pairs you need to consider, and each pair takes O(CNT_PRODUCTS) time to process. The brute-force approach is thus a cubic O(SHOPS*SHOPS*CNT_PRODUCTS) algorithm per meal.

    /* Let Q, C, X represent quantity and cost of item 
     * with row number indicating shop number. 
     * Let X be the current meal
     */
    public static int cost(final int CNT_PRODUCTS, int[][] Q, int[][] C, int[] X, int i1, int i2) {
        // Precondition: Must satisfy quantity constraints
        int cost = 0;
        int i1st, i2nd;
        for (int k = 0; k < CNT_PRODUCTS; k++) {
            // Two shops
            if (i1 < i2) {
                // Determine which shop is priority for thhis item
                if (C[i1][k] < C[i2][k]) {
                    i1st = i1;
                    i2nd = i2;
                }
                else {
                    i1st = i2;
                    i2nd = i1;
                }
                // Add items to shop
                if (Q[i1st][k] >= X[k]) {// If the first shop supplies all
                    cost += X[k]*C[i1st][k];
                    System.out.printf("\tBought %d unit%d all from shop #%d for $%d each.\n", X[k], k, i1st, C[i1st][k]);
                }
                else { // When both shops are required
                    cost += Q[i1st][k]*C[i1st][k];
                    cost += (X[k] - Q[i1st][k])*C[i2nd][k];
                    System.out.printf("\tBought %d unit%d from shop #%d for $%d each.\n", Q[i1st][k], k, i1st, C[i1st][k]);
                    System.out.printf("\tBought %d unit%d from shop #%d for $%d each.\n", X[k] - Q[i1st][k], k, i2nd, C[i2nd][k]);
                }
            }
            // One shop
            else {
                cost += X[k]*C[i1][k];
                System.out.printf("\tBought %d unit%d from shop #%d for $%d each.\n", X[k], k, i1, C[i1][k]);
            }
        }
        System.out.printf("\tTotal cost is $%d\n\n", cost);
        return cost;
    }

Optimization

You can determine S once given a list of meals, and determine satisfiability by looking up the S[][][k].

Although I did see that this problem is claimed to be dynamic programming, I don't see an optimal substructure.