I code the offers as bitmaps and calculate the cost of every bitmap. This gives 2^N configurations. Then the algorithm is dynamic programming or minimum path in a directed acyclic graph.
   Please help me see where I am wrong.

   Here's part of my code

/* variables */

int prices[maxn];

struct offer {
    int tapcode;
    short int  price;
} offers[maxm];

int N, M, goal;

short int cost[1 << maxn];

void solve(void)
{
    int tapcodemax = 1 << N;
    int i, tapcode, k, j, sol;
    short int ccost;

    /* compute initial costs based on individual prices */

    for (i = 0; i < tapcodemax; i++) {
        tapcode = i, ccost = 0;
        for (j = 0; j < N; j++, tapcode /= 2)
            if (tapcode & 1)
               ccost += prices[j];
        cost[i] = ccost;
    }

    /* consider special offers */

    for (i = 0; i < tapcodemax; i++)
        for (k = 0; k < M; k++)
            if (cost[i | offers[k].tapcode] > cost[i] + offers[k].price)
               cost[i | offers[k].tapcode] = cost[i] + offers[k].price;

    for (sol = cost[goal], i = 0; i < tapcodemax; i++)
        if (((i & goal) == goal) && sol > cost[i])
           sol = cost[i];
    printf ("%d\n", sol);
}

Edited by author 30.08.2004 01:48

This part which you give is right ... maybe the inital part is wrong..