0/1 Knapsack and colored items with conditions

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Hello cf,

I'm trying to solve this 0/1 Knapsack problem:

We have N items with each item characterized by weight, price and color (white, blue, red or black).

We have to choose 12 items with maximum total price such as the sum of their weights is <= W and the choosed items fullfill these conditions:

only 1 white item
between 3 and 5 blue items
between 3 and 5 red items
between 1 and 3 black items

I tried this backtracking solution (take or leave current item and continue) wich work fine:

Backtrck solution

int go(int i, int numW, int numBlue, int numR, int numBlack, int currWeight) {
    if (i == N)
        // checkMin check that we have the minumum number of each colored item
        return (checkMin(numW, numBlue, numR, numBlack) && numW + numBlue + numR + numBlack == 12) ? 0 : -10000; 
    int res = -10000;
    res = max(res, go(i + 1, numW, numBlue, numR, numBlack, currWeight));
    //canAddItem check if we can add current item without exceeding the max Weight and not excedding the max number of each colored item
    if (canAddItem(items[i], numW, numBlue, numR, numBlack, currWeight)) {  
        if (items[i].color.equals("W")) numW++;
        if (items[i].color.equals("Blue")) numBlue++;
        if (items[i].color.equals("R")) numR++;
        if (items[i].color.equals("Black")) numBlack++;
        res = max(res, items[i].value + go(i + 1, numW, numBlue, numR, numBlack, (items[i].weight + currWeight)));
    }
    return res;
}

boolean checkMax(int numW, int numBlue, int numR, int numBlack) {
    return numW <= 1 && numBlue <= 5 && numR <= 5 && numBlack <= 3;
}

boolean checkMin(int numW, int numBlue, int numR, int numBlack) {
    return numW == 1 && numBlue >= 3 && numR >= 3 && numBlack >= 1;
}

boolean canAddItem(Item item, int numW, int numBlue, int numR, int numBlack, int currWeight) {
    if (item.color.equals("W")) numW++;
    if (item.color.equals("Blue")) numBlue++;
    if (item.color.equals("R")) numR++;
    if (item.color.equals("Black")) numBlack++;
    currWeight += item.cost;
    return checkMax(numW, numBlue, numR, numBlack) && currWeight <= W && numW + numDef + numMid + numAtt <= 12;
}

This work fines but with an exponential complexity so I tried to add memoization (caching: dp[i][currWeight][numW][numBlue][numR][numBlack]) but it doesn't work anymore.

Can any body explain why the memoization doesn't work here, or share his personal approach to solve this problem ?

Costraints:

N <= 100 W <= 1000

PS I've seen this problem somewhere before but I don't have a link, can anybody provide a link of a similiar problems ?