我有两个背包,称它们为背包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和价格都要除以部分。
我应该如何实现这个目标?
我尝试修改一个分数背包算法,但我不知道需要修改哪些部分/怎样修改才能实现我的目标。
c1*X1 + c2*X2 + ... = 10
,其中c1
,c2
等是物品1,物品2等的数量。第二个方程是c1*Y1 + c2*Y2 + ... = 20
,使用与第一个方程相同的值c1
,c2
等。第三个方程是c1*P1 + c2*P2 + ...
,你想要最小化它。这似乎是一个线性规划问题。 - user3386109