背包问题

August 8, 2018 · View on GitHub

背包问题 是 组合优化中 的问题: 给定一组项目,每个项目具有 重量 和值,确定要包括在集合中的每个项目的数量.

使总重量 小于或等于 给定极限,总值尽可能大.

它的名字来源于 受到固定尺寸背包约束的人 所面临的问题,并且必须 用最有价值的物品填充它.

背包就那么大, 到底怎么选择装什么东西, 价值才最大.

一维 (约束) 背包问题的示例: 应选择 哪些方框以最大化金额,同时仍保持 总重量 低于或等于15公斤?

knapsack problem

定义

0/1背包问题

最常见的问题是0/1背包问题,这限制了每种物品xi的数量为 0 或者 1 份.

给定n个项目编号为1到n作一组,每个都有一个重量wi和一个价值vi,剩下最大的重量容量W,

最大化价值0/1 knapsack

受制于0/1 knapsack 不能大于最大容量和0/1 knapsack每种选择只能小于或等于1

这里xi表示在背包里 第i个项目. 普遍来说,问题是 最大化背包物品价值的总和,且使得 重量的总和 小于或等于 背包的容量.

有界背包问题 (BKP)

该 有界背包问题 (BKP) 消除了每个项目只有一个的限制,但限制了xi的数量为 最大非负整数值c:

最大化bounded knapsack

受制于bounded knapsack和bounded knapsack

无界背包问题 (UKP)

该 无界背包问题 (UKP) 每种物品的副本数量没有上限,除上述限制外,xi是一个非负整数.

最大化unbounded knapsack

受制于unbounded knapsack和unbounded knapsack

参考