0/1 Knapsack and colored items with conditions

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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 weight 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("B")) numBlue++;
        if (items[i].color.equals("R")) numR++;
        if (items[i].color.equals("B")) numBlack++;
        res = max(res, players[i].value + go(i + 1, numW, numBlue, numR, numBlack, (items[i].weight + currWeight)));
    }
    return res;
}

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 ?