c++ - 多重约束背包

Question

我正在尝试解决以下问题:

输入:

1. 一个项目数组，每个项目有3个不同的权重(整数)、一个值和该类型项目的可用数量 .
2. 每种重量的最大值

输出:

1. 一个数组，它告诉每个项目要取多少才能达到最大值。每件元素的每件重量总和不得超过允许的最大重量，并且您不能多拿一件可用的元素。

示例输出:{3,0,2,1} 表示 item1 中的 3 个，item2 中的 0 个， 中的 2 个item3，以及 item4 的 1 个。

示例场景:

如果我对解释不是很清楚，想象它是关于将食物放在背包上。每种食物都有重量、体积、卡路里数量和值(value)，每种食物都有一定数量。目标是在不超过特定最大重量、体积和卡路里的情况下，最大化背包中食物的值(value)。

在这种情况下，INPUT 可能是:

Array<Food>:

• 汉堡(重量 2，体积 2，卡路里 5，值(value) 5 美元，汉堡数量 3)
• 披萨(重量 3，体积 7，卡路里 6，值(value) 8 美元，披萨数量 2)
• 热狗(重量 1，体积 1，卡路里 3，值(value) 2$，热狗数量 6)

int MaxWeight = 10; int 最大音量 = 15; int 最大卡路里 = 10;

我的尝试

由于数据集很小(假设有 7 种商品，每种商品最多 15 件)，我想到了暴力搜索:

• 跟踪迄今为止找到的最佳集合(最有值(value)但不超过任何限制)，调用最佳集 B
• 有一个递归函数R(s)，它接受一个集合(每个项目有多少的数组)作为输入，如果输入无效，它返回。如果输入有效，它首先更新 B(如果 s 比 B 好)，然后调用 R(s + p_i) 对于每个产品 p_i

想法是首先调用 R(s)，其中 s = 空集(每个产品为 0)，然后将创建每个可能的分支，同时忽略超过权重的分支。

这显然是行不通的，因为即使只有 7 个项目，必须检查的分支数量也很大

非常感谢任何帮助!

Answer 1

您必须考虑 DP 方法中的每种权重。我将用 C++ 编写实现:

vector<Food> Array;
int memo[MAX_ITEM][MAX_WEIGHT1][MAX_WEIGHT2][MAX_WEIGHT3];
int f(int ind, int weight1, int weight2, int weight3){
    if(weight1<0 || weight2<0 || weight3<0) return -INF;
    if(ind == Array.size()) return 0;
    int &ret= memo[ind][weight1][weight2][weight3];
    if(ret>0) return ret;
    int res = 0;
    for(int i=0;i<=Array[ind].maxOfType;i++)
        res = max(res, i * Array[ind].value + f(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3));
    return ret = res;
}

DP函数是递归的，我们使用memoization优化它。它返回我们可以获得的最大值。你可以通过以下方式调用它:

f(0,MaxWeight1, MaxWeight2, MaxWeight3);

之后，我们必须跟踪并查看哪些项目带来了最大值(value)。 Next 方法将打印您想要的内容:

void printResult(int ind, int weight1, int weight2, int weight3){
        if(ind == Array.size()) return;
        int maxi = memo[ind][weight1][weight2][weight3];
        for(int i=0;i<=Array[ind].maxOfType;i++){
            int cur = i * Array[ind].value + f(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3);
            if(cur == maxi){
                cout<<i<<", ";
                printResult(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3);
                break;
            }
        }
}

所有代码都经过测试并且运行良好。