Optimal Selection for minimum total sum

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];
}

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 ]

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]);

}