我正在尝试制定一种算法(可能使用Python中的OR工具(来解决一个似乎与背包问题有关的问题。
- 我在位置a有一套物品
- 我想把他们送到B地点
- 每个项目都有一个重量和一个值
- 我只能承受X的重量
- 我害怕一路上被抢，所以我只想携带最多Y的价值
如果我正试图计划从地点A到地点B的第一次旅行，我如何选择以下项目：
- 我最大化装载的重量，最高限制为X(最大限度地减少浪费的重量(
- 我最大化加载的值，最高限制为Y(最大限度地减少浪费的值容量(
一个人为的例子：
- 我的极限是5公斤和50美元
- 我有10件C(重量：0.1公斤，价值：10美元(
- 我有10件D(重量：1公斤，价值：1美元(
；"容易"；解决方案是进行4次旅行：
- 5倍项目C(50美元，0.5公斤(
- 5x项目C(50美元，0.5公斤(
- 5倍项目D(5.5公斤(
- 5倍项目D(5.5公斤(
但更明智的解决方案是只进行3次旅行：
- 4件C+4件D(44美元，4.4公斤(
- 4件C+4件D(44美元，4.4公斤(
- 2件C+2件D(22美元，2.2公斤(
我使用过OR Tools线性解算器，但仅在具有多个约束的情况下最大化一个值。如何在多个约束条件下最大化多个值(加载重量和加载值(？
我相信我找到了解决方案。我所做的是试图最大化一个既考虑权重又考虑价值的复合变量。在Python中使用OR工具：
objective = solver.Objective()
for i, item in enumerate(item_list):
objective.SetCoefficient(x[i], item['mass']/max_volume + item['value']/max_value)
objective.SetMaximization()
这将系数设置为同时考虑质量和值。重要的部分是，每一个都是针对其相关的极限进行归一化的。该解决方案始终为我提供一组项目，这些项目充分利用了权重和价值；空间"；充分发挥作用。