Optimal Selection for minimum total sum

Question

This is a problem from competitive programmer's handbook:
We are given the prices of k products over n days, and we want to buy each product exactly once. However, we are allowed to buy at most one product in a day. What is the minimum total price?

Day	0	1	2	3	4	5	6	7
Product 0	6	9	5	2	8	9	1	6
Product 1	8	2	6	2	7	5	7	2
Product 2	5	3	9	7	3	5	1	4

The Optimal Selection is:

• product 0 on day 3 at price 2,
  
• product 1 on day 1 at price 2,
  
• product 2 on days 6 at price 1.
  

which gives us the total of 5.

The solution:
We either do not buy any product on day d or buy a product x that belongs to set S. In the latter case, we remove x from set S and add the price of x to the total price.

Here's the code from book:

#include <stdio.h>
#ifndef min
    #define min(a, b) ((a) < (b) ? (a) : (b))
#endif

int main()
{
    int price[3][8] = {{ 6, 9, 5, 2, 8, 9, 1, 6 },
                       { 8, 2, 6, 2, 7, 5, 7, 2 },
                       { 5, 3, 9, 7, 3, 5, 1, 4 }};
    int n = 8, k = 3;
    int total[1<<10][10];
    //Buy all products on day 0
    for (int x = 0; x < k; x++) {
        total[1<<x][0] = price[x][0];
    }

    for (int d = 1; d < n; d++) {
        for (int s = 0; s < (1<<k); s++) {
            total[s][d] = total[s][d-1];
            for (int x = 0; x < k; x++) {
                if (s & (1<<x)) {
                    total[s][d] = min(total[s][d], total[s ^ (1<<x)][d-1] + price[x][d]);
                    break;
                }
            }
        }
    }
    //Output    
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf("%d", total[i][j]);
        }
        printf("\n");
    }
}

The problem restricts us to buy only one product a day but the code seems to not address that issue at all (also, we buy all products on first day which is fine). The output is just the minimum for each product available by that day [1,2,1]. What am I doing wrong here?

Answer 1

After quite a bit of time in the debugger I was able to make the algo from the book work. Suffice to say the snippet provided in the book is completely broken.

Most major edits:

1. we will only update a more complex sum if we are updating it from an adjacent sum, that is, we do not update a sum at 111 from the sum of 001 or 010. We use __builtin_popcount to find the difference between the current set index and the one we are tryign to update from.

2. we will only update higher order sets if enough days has passed for prior sets to be filled.

I hope that I didn't make a mistake here(again). If I did, feel free to correct me. I did try to verify multiple inputs this time and this seems to be working.

Note that I am using multiple local variables that are completely unnecessary. I just wanted some clarity and readability.

This is essentially the same algorithm as in the book, but with a set of restrictions necessary for it to function correctly. Without those restrictions it adds up completely incompatible stuff or adds up at the wrong time and ends up not working.

The algo does address that you can only buy 1 item a day in the sol[xorIndex][dayIndex-1] + currentPrice part. The sol part being accessed was filled on previous days with items excluding the one we are adding.

int optimalSelection(int products, int days, int prices[products][days]){
    int sol[1<<products][days];
    memset(sol, 0, sizeof(sol));
    for (int x = 0; x < products; x++) {
        sol[1<<x][0] = prices[x][0];
    }

    for (int dayIndex = 1; dayIndex < days; dayIndex++) {
        int allPossibleSetsCount = 1<<products;
        for (int setIndex = 0; setIndex < allPossibleSetsCount; setIndex++) {
            int currentMin = sol[setIndex][dayIndex-1];
            for (int productIndex = 0; productIndex < products; productIndex++) {
                if (setIndex&(1<<productIndex)) {
                    // this is the index of the set WITHOUT current product
                    int xorIndex = setIndex^(1<<productIndex);
                    if(__builtin_popcount(xorIndex) > dayIndex)
                        continue;

                    if (__builtin_popcount(setIndex ^ xorIndex) == 1){
                        // minimum for the prior day for the set excluding this product
                        int previousMin = sol[xorIndex][dayIndex-1];
                        // current price of the product
                        int currentPrice = prices[productIndex][dayIndex];
                        sol[setIndex][dayIndex] = currentMin == 0 ? previousMin + currentPrice : std::min(previousMin + currentPrice, currentMin);
                        currentMin = sol[setIndex][dayIndex];
                    }

                }
            }
        }
    }

    return sol[(1<<products)-1][days-1];
}

Answer 2

The posted algorithm has a time and space complexity of n.k.2^k which seems very expensive and likely to cause a stack overflow for moderately large sets.

Furthermore, the output is not very informative and the constraint at most one product per day does not seem enforceable.

Here is an alternative approach using recursion, with similar time complexity n^k but a much smaller memory footprint:

#include <stdio.h>

enum { N = 8, K = 3 };

struct optim {
    const int (*price)[N];
    int bestsol[K];
    int bestprice;
};

void test(struct optim *p, int i, int set, int price, int *sol) {
    if (i >= K) {
        if (p->bestprice > price) {
            p->bestprice = price;
            for (int j = 0; j < K; j++) {
                p->bestsol[j] = sol[j];
            }
        }
    } else {
        for (int d = 0; d < N; d++) {
            if (set & (1 << d)) {
                continue;  // constaint: only 1 product per day
            }
            sol[i] = d;
            test(p, i + 1, set | (1 << d), price + p->price[i][d], sol);
        }
    }
}

int main() {
    int price[K][N] = { { 6, 9, 5, 2, 8, 9, 1, 6 },
                        { 8, 2, 6, 2, 7, 5, 7, 2 },
                        { 5, 3, 9, 7, 3, 5, 1, 4 } };
    struct optim data = { price, { 0, 1, 2 }, price[0][0] + price[1][1] + price[2][2] };
    int sol[K];

    test(&data, 0, 0, 0, sol);
    printf("price: %d, days: [", data.bestprice);
    for (int i = 0; i < K; i++) {
        printf(" %d", data.bestsol[i]);
    }
    printf(" ]\n");
    return 0;
}

Output: price: 5, days: [ 3 1 6 ]

Answer 3

Turns out the solution that was provided in the book was incomplete. For the program to return the correct result, all subsets of first day have to be populated but in the book only the subsets containing single element that were mapped to powers of two i.e., the indices 1,2,4,etc of total[][] were populated which left the other subsets to have value of 0. This made each of the subsequent day calculation to take minimum value which is 0. code in line 14 to 16

for (int x = 0; x < k; x++) {
        total[1<<x][0] = price[x][0];
    }

must be replaced with:

  for (int s = 0; s < (1 << k); s++) {
    for (int x = 0; x < k; x++) {
      if (s & (1 << x)) {
        total[s][0] = price[x][0];
      }
    }
  }

Minimum Total Sum for each day will be the set that contains all the elements i.e. total[(1<<k)-1][index of day]. With all the changes the working code is:

#include <stdio.h>

#ifndef min
 #define min(a, b)((a) < (b) ? (a) : (b))
#endif

int main()
{
    int price[3][8] = {
        { 6, 9, 5, 2, 8, 9, 1, 6 },
        { 8, 2, 6, 2, 7, 5, 7, 2 },
        { 5, 3, 9, 7, 3, 5, 1, 4 }
    };
    int n = 8, k = 3;

    //Changed to scale with input
    int total[1 << k][n];

    //Buy all products on day 0
    //Changes here
    for (int s = 0; s < (1 << k); s++)
    {
        for (int x = 0; x < k; x++)
        {
            if (s &(1 << x))
            {
                total[s][0] = price[x][0];
            }
        }
    }

    for (int d = 1; d < n; d++)
    {
        for (int s = 0; s < (1 << k); s++)
        {
            total[s][d] = total[s][d - 1];
            for (int x = 0; x < k; x++)
            {
                if (s &(1 << x))
                {
                    total[s][d] = min(total[s][d], total[s ^ (1 << x)][d - 1] + price[x][d]);
                    break;
                }
            }
        }
    }

    //Output
    //Changes here    
    printf("%d", total[(1 << k) - 1][n - 1]);

}