0/1 背包和有条件的彩色物品

Question

我正在尝试解决这个 0/1 背包问题：

我们有 N 件商品，每件商品都有重量、价格和颜色（白色、蓝色、红色或黑色）。

我们必须选择总价最高的12件商品，例如它们的重量之和<= W以及所选商品满足这些条件：

只有 1 件白色物品
3 到 5 个蓝色物品
3 到 5 个红色项目
1 到 3 个黑色项目

我尝试了这个回溯解决方案，效果很好：

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

这项工作很好，但复杂度呈指数级增长，因此我尝试添加记忆（缓存），但它不再起作用了。

没有记忆的回溯，给出正确答案：https://ideone.com/aPdZjZ

相同的代码和输入但使用记忆给出了错误的答案：https://ideone.com/wPqxBG

任何人都可以解释为什么记忆在这里不起作用，或者分享他解决这个问题的个人方法吗？

Answer 1

您正在修改状态变量，例如 DP 解决方案中 go 函数中的 numW, numBlue, etc.。尝试 here。进行以下更正后，它似乎起作用了。还没有检查整体正确性，但回溯和 DP 解决方案都给出了相同的答案。

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

0/1 背包和有条件的彩色物品

0/1 Knapsack and colored items with conditions

algorithm

knapsack-problem

dynamic-programming