多重约束背包

Question

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

输入：

一组项目，每个项目有 3 种不同的权重（整数），一个值和数量有此类商品.
每种重量的最大值

输出：

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

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

示例场景：

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

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

Array<Food>:

汉堡（重量 2，体积 2，卡路里 5，价值 5$，汉堡数量 3）
披萨（重量 3，体积 7，卡路里 6，价值 8 美元，披萨数量 2）
热狗（重量 1，体积 1，卡路里 3，价值 2$，热狗数量 6）

int MaxWeight = 10; int MaxVolume = 15; int MaxCalories = 10;

我的尝试

由于数据集很小（比如7种物品，每种物品最多15件），我想到了暴力搜索：

跟踪迄今为止找到的最佳集合（最有价值但不是超过任何限制），调用最佳设置 B
有一个递归函数R(s)，它以一个集合（每项有多少的数组）作为输入，如果输入无效，它returns。如果输入有效，它首先更新 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对其进行优化。它returns我们可以得到的最大值。您可以通过以下方式调用它：

f(0,MaxWeight1, MaxWeight2, MaxWeight3);

之后我们必须跟踪并查看哪些项目带来了最大价值。 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;
            }
        }
}

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

多重约束背包

Multiple Constrain Knapsack

c++

algorithm

knapsack-problem

dynamic-programming

backtracking

输入：

输出：

示例场景：

我的尝试