使用相同物品填充两个分数背包

Question

我有两个背包，称它们为背包A和背包B，每个背包都有一个最大重量限制。我们还有一些物品类型可以带上旅途。每种物品类型都有一个价格和两个值 - 值X和值Y。每当使用时，这些值之一就会被添加到相应的背包中，因此以下内容是正确的：

我们将遵循以下限制（请注意，这不是解决方案，只是核心原则的示例）：

Knapsack A
    capacity: 10
Knapsack B
    capacity: 20

items:
Item 1
    price: 10
    X: 3
    Y: 9

当我们“拿取”物品1后，我们得到了以下背包状态:

Knapsack A 
    remaining capacity: 7 (capacity of A - X of item 1)
Knapsack B
    remaining capacity: 11 (capacity of B - Y of item 1)

为达到此状态，我们支付了10个单位（Item 1的价格）。

我们试图找到最佳的物品组合（我们可以无限次使用每种物品），以使两个背包都完美地填满，且价格最低。我们可以使用每种物品的部分，这意味着X、Y和价格都要除以部分。

我应该如何实现这个目标？

我尝试修改一个分数背包算法，但我不知道需要修改哪些部分/怎样修改才能实现我的目标。

- adamsass

---

我认为这与背包问题无关。你基本上有三个方程式。一个方程是 c1*X1 + c2*X2 + ... = 10，其中 c1，c2 等是物品1，物品2等的数量。第二个方程是 c1*Y1 + c2*Y2 + ... = 20，使用与第一个方程相同的值 c1，c2 等。第三个方程是 c1*P1 + c2*P2 + ...，你想要最小化它。这似乎是一个线性规划问题。 - user3386109

Answer 1

正如用户3386109所述，存在一个简单的线性方案。

对于每个项目i，令u_i ≥ 0为购买i的（分数）单位数量。 我们想要

最小化∑_i price_i u_i

（最小化i项产品价格和i购买数量的乘积之和），遵循线性约束条件确保我们完全填充两个背包：

A: ∑_i X_i u_i = 容量_A
B: ∑_i Y_i u_i = 容量_B。

现在，您可以编写一个程序来扩展这些总和，并将结果方程式交给求解器库。我在工作中使用GLOP;以下是示例代码。

如果您不想使用现成的求解器，这个线性规划问题非常特殊，因为它只有两个约束条件，所以可能有一种专门的算法（例如，也许我们可以使用Megiddo的低维LP算法来解决对偶问题）。但它并不像分数背包问题那么简单。

import collections

from ortools.linear_solver import pywraplp


Item = collections.namedtuple("Item", ("price", "X", "Y"))


def optimize(A, B, items):
    solver = pywraplp.Solver.CreateSolver("GLOP")
    quantities = [solver.NumVar(0, solver.infinity(), "") for i in items]
    solver.Minimize(sum(i.price * u for (i, u) in zip(items, quantities)))
    solver.Add(sum(i.X * u for (i, u) in zip(items, quantities)) == A)
    solver.Add(sum(i.Y * u for (i, u) in zip(items, quantities)) == B)
    solver.Solve()
    return solver.Objective().Value(), [
        (i, u.solution_value()) for (i, u) in zip(items, quantities)
    ]


def test():
    obj_value, quantities = optimize(
        10,
        20,
        [Item(price=10, X=3, Y=9), Item(price=5, X=5, Y=7), Item(price=100, X=1, Y=1)],
    )
    print("# cost: {}".format(obj_value))
    for i, u in quantities:
        print("# {}: {}".format(i, u))


if __name__ == "__main__":
    test()

# cost: 18.750000000000007
# Item(price=10, X=3, Y=9): 1.250000000000001
# Item(price=5, X=5, Y=7): 1.2499999999999991
# Item(price=100, X=1, Y=1): 0.0

- David Eisenstat

---

谢谢回复！您能否详细说明一下可能的解决方案（例如使用GLOP）？我以前从未使用过它，但是从链接中我认为我知道如何插入约束条件，但我不确定如何制定由物品形成的单个方程。谢谢。 - adamsass

@adamsass，我为你写了一些代码。 - David Eisenstat