Filling two fractional knapsacks using the same items

I have two knapsacks, let's call them knapsack A, and knapsack B, each knapsack has a max weight limit. We also have some item types that we can take with us. Each item type has a price, and two values - value X, and value Y. Each of these values is added to it's respective knapsack when used, so that the following is true:

We are operating with the following limits (note that this is not a solution, just an example of the core principle):

Knapsack A
    capacity: 10
Knapsack B
    capacity: 20

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

After we 'take' Item 1 we get the following knapsack state:

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

To reach this state we have paid 10 units (price of Item 1).

We're trying to find the best combination of items (we may use each item an infinite amount of times) so that we fill both knapsacks perfectly, and at the lowest possible price. We may use fractions of each item, this means that X, Y, and price all get divided by the fraction.

How can I achieve this?

I have tried modifying a fractional knapsack algorithm, but I don't know what parts/what to modify in order to achieve my goals.

As user3386109 notes, there is a straightforward linear program.

For each item i, let u_i ≥ 0 be the (fractional) number of units purchased of i. We want to

minimize ∑_i price_i u_i

(minimize the sum over items i of the product of the price of i and the purchase quantity of i), subject to linear constraints ensuring that we exactly fill both knapsacks:

A: ∑_i X_i u_i = capacity_A
B: ∑_i Y_i u_i = capacity_B.

Now, you can write a program to expand the sums and hand the resulting equations off to a solver library. I use GLOP at work; sample code below.

If you don’t want to use an off-the-shelf solver, this linear program is quite special in that it only has two constraints, so there’s likely a specialized algorithm (e.g.,  maybe we could use Megiddo’s low-dimensional LP algorithm to solve the dual). But it won’t be as simple as fractional knapsack.

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