algorithm - 具有两个约束的背包问题的伪代码算法
问题描述
我正在尝试用两个约束来解决以下背包问题。
我们所知道的:
- 列表项 项总数
- 列表项重量
- 列表项值
- 列出项目如果项目是否易碎(真/假)
约束:
- 清单项目最大背包重量
- 列表项 背包可容纳的易碎物品的最大数量。
谁能给我一些关于我应该使用的算法、伪代码或好文章的建议?
更新:
我忘了提到的重要一点是,我还需要知道我把哪些物品放在了包里。
解决方案
看起来对背包的修改可以解决它。
假设我们有 N 个物品,最大背包重量为 W,最大易碎物品数量为 F
让我们将 dp 表定义为 3 维数组 dp[N+1][W+1][F+1]
现在 dp[n][w][f] 存储我们可以得到的最大值,如果我们用前 n 个项目的一些项目子集填充背包,重量为 w 且有 f 个易碎物品。
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;
}
推荐阅读
- c++ - G ++编译器错误?
- shell - 如果 Makefile 中的条件无法运行
- javascript - Vue 模型绑定为数字
- java - Apache kafka - 手动确认(AbstractMessageListenerContainer.AckMode.MANUAL)不起作用并且在库升级时重播事件
- azure - 将自定义技能合并到一个解决方案中
- spring - Spring Cloud 过多的健康检查线程导致应用宕机
- ms-access - Azure 数据工厂 - MS Access 作为源数据库 - 错误
- java - Hibernate 中的批量更新
- javascript - 在 vaadin 14 中集成 facebook 共享链接
- python - Python - 尝试按年份分组并汇总销售数据时出错