具有两个约束的背包问题的伪代码算法

Question

我试图通过两个约束解决以下背包问题。

我们所知道的：

• 列表项目总项目数
• 列表项目重量
• 列表项值
• 列表项如果项目是否易碎（是/否）

限制：

• 列表项目背包的最大重量
• 列表项目背包可以包含的最大易碎物品数量。

任何人都可以给我一些关于我应该使用的算法，伪代码或好文章的建议吗？

更新：

我忘记提到的重要一点是，我还需要知道我放在包里的物品。

Answer 1

看起来对背包的修改会解决它。

假设我们有N个项目，最大背包重量为W，最大易碎物品数量为F.

让我们将dp表定义为三维数组dp [N + 1] [W + 1] [F + 1]

现在dp [n] [w] [f]存储我们可以得到的最大值，如果我们用前n个项目的一些子集填充背包，具有正好w的权重并且具有正好脆弱的项目。

frop dp [n] [w] [f]我们可以转到州：

• dp [n + 1] [w] [f]如果我们跳过第n + 1项
• dp [n + 1] [w + weight（n + 1）] [f + isFragile（n + 1）]如果我们取第n + 1项

所以伪代码：

dp[N+1][W+1][F+1] // memo table, initially filled with -1

 int solve(n,w,f)
{
    if(n > N)return 0;
    if(dp[n][w][f] != -1) return dp[n][w][f];

    dp[n][w][f] = solve(n+1,w,f); //skip item
    if(w + weight(n) <= W && f + isFragile(n) <=F)
    dp[n][w][f] = max(dp[n][w][f], value(n) + solve(n+1, w + weight(n), f + isFragile(n)));

    return dp[n][w][f]
}

print(solve(1,0,0))

获得实际的子集也并不困难：

vector<int> getSolution(n,w,f)
{   
    int optimalValue = solve(n,w,f);
    vector<int>answer; //just some dynamic array / arrayList

    while(n <= N)
    {
        if(solve(n+1,w,f) == optimalValue)n++; //if after skipping item we can still get optimal answer we just skip it
        else //otherwise we cant so current item must be taken
        {
            int new_w = w + weight(n);
            int new_f = f + isFragile(n);
            answer.push_back(n); //so we just save its index, and update all values
            optimalValue -= value(n);
            n++;
            w = new_w;
            f = new_f;
        }
    }
    return answer;
}