CODEWITHSUNDEEP
algorithmdynamic-programmingknapsack-problem
Abdennacer Lachiheb
Abdennacer Lachiheb

Reputation: 4888

0/1 Knapsack and colored items with conditions

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 chosen items fulfill these conditions:

I tried this backtracking solution which work fine:

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) but it doesn't work anymore.

Backtrack without memoization, gives correct answer: https://ideone.com/aPdZjZ

Same code and input but with memoization gives wrong answer: https://ideone.com/wPqxBG

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

Upvotes: 1

Views: 233

Answers (1)

รยקคгรђשค
รยקคгรђשค

Reputation: 1979

You are modifying state variables like numW, numBlue, etc. in go function in your DP solution. Try here. After making the below correction, it seems to work. Haven't checked overall correctness but the backtracking and DP solution both give same answer.

    if (canAddItem(items[i], numW, numBlue, numR, numBlack, currSpent)) {
        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].cost + currSpent)));
        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--;            
    }

Upvotes: 2

Related Questions