具有适当比率约束和重量约束的背包算法

Question

问题：您是一名果汁制造商，正在为您的业务寻找最佳供应商。供应商销售的浓缩物含有 3 种成分：X:Y:Z 不同比例。你的果汁需要有1:1:1这样的比例，否则就不好吃了。浓缩物的重量是其成分的总和（以磅为单位），所有供应商都以相同的价格出售他们的浓缩物，但是您的卡车最多只能运载 400 磅的浓缩物。为您的业务寻找最佳供应商：购买（寻找）尽可能多磅的浓缩物（但少于 400 磅），要知道 1:1:1 以外的成分比例是不可接受的。

输入：第一行告诉你市场上卖了多少精矿（少于200）接下来的 n 行是关于 X:Y:Z 浓缩物成分的比例（以磅为单位）

输出：第一行应该是您要购买的浓缩物成分的重量总和（小于 400 磅）第二行应该告诉你必须购买多少浓缩物才能使这个数量保持适当的比例

示例：

in:
4 //how many concentrates are sold on the market
1 2 3 //first concentrate contains 1lb of X, 2lbs of Y, 3 lbs of Z
0 4 1
1 3 4
1 1 1
2 1 0

out: 
12 //4lbs of ingredient X + 4lbs Y + 4lbs Z
3 //we're buying three concentrates: the first one, fourth and fifth (1 2 3; 1 1 1; 2 1 0) so we're getting the biggest amount of it with 1:1:1 ratio of ingredients

我的解决方法：我的解决方案是一种蛮力方法，当有很多供应商时速度非常慢，因为它的复杂性是 2^(n-2) - 这个算法只会创建我们可以购买的浓缩物的所有可能组合，它会检查他们是否比例是 1:1:1，如果是，那么它会比较它们并找到总成分量最多的那个，总重量不到 400 磅。

我正在寻找一种动态逼近算法，但是，我不知道如何使用适当的比率约束来实现它。

Answer 1

400/3 = 133 这意味着答案中的任何成分都不能超过 133 磅。所以 DP 数组是 array[134][134][134]，其中数组中的每个条目都是要购买的浓缩物数量，以实现该组合。

那个数组里面有大约240万个条目，每个输入（少于200个）需要扫描一次数组。所以你正在寻找大约 5 亿次操作来填充数组。这在现代计算机上是合理的。

数组填满后，简单扫描即可找到答案

for ( i = 133; i > 0; i-- )
    if ( array[i][i][i] > 0 )
        the answer is array[i][i][i]

Answer 2

与 user3386109 的好主意相比，这里有一种方法可能会让我们的操作复杂性更低。分别为三元组的每个成员进行总和枚举，并跟踪三个枚举组合的（索引，基数）匹配：对于三元组的每个成员，x、y 和 z in (x,y,z) 迭代一个单独的一维数组表示总和为 133，索引基数：

# for example, Xs enumeration only
for index, (x,y,z) in triples:
  for s in [133 - x ... 0]
    if sums_x[s].cardinalities.length > 0:
      for cardinality in sums_x[s].cardinalities:
        sums_x[s + x].by_index.add( (index,cardinality + 1) ) # this is a set of (index,cardinality) tuples
        sums_x[s + x].cardinalities["cardinality + 1"].push( index ) # hash cardinality to indexes

  sums_x[x].by_index.add( (index,1) )
  sums_x[x].cardinalities["1"].push( index )

一旦我们迭代了三个一维数组，一个对应三元组的每个成员，我们就可以追踪可能的匹配项。由于在所有三个枚举中跟踪 (sum,cardinality,index) 的一致匹配的可能性很低，因此这些情况很少见。

例如：

(1 2 3),(0 4 1),(1 3 4),(1 1 1),(2 1 0)

index = 0
sums_x[1].by_index = {(0,1)} # (index,cardinality)
sums_x[1].cardinalities = {"1": [0]} # cardinality: indexes

index = 1
sums_x[0].by_index = {(1,1)} # (index,cardinality)
sums_x[0].cardinalities = {"0,1": [1]} # cardinality: indexes
sums_x[1].by_index = {(0,1), (1,2)}
sums_x[1].cardinalities = {"1": [0], "2": [1]}

...

index = 4
sums_x[4].by_index = {(4,3), (4,4)} # (index,cardinality)
sums_x[4].cardinalities = {"2": [3], "3": [4], "4": [4]} # cardinality: indexes

sums_y[4].by_index = {(1,1), (3,2), (4,2), (4,3)}
sums_y[4].cardinalities = {"1": [1], "2": [3,4], "3": [4]}

sums_z[4].by_index = {(1,2), (2,1), (3,2), (4,3), (4,2)}
sums_z[4].cardinalities = {"2": [1,3,4], "1": [2], "3": [4]}

正如我们所见，对于本例中的和 4，在所有三个和结构 (4,3) 中只有一个 (index,cardinality) 匹配，然后我们可以使用关联的值：

sums_z[4]: 4,3 
  => val 0 => lookup by z sum (4 - 0) and cardinality (3 - 1) 
  => sums_z[4].cardinalities[2] yields only one match across: index 3
  => lookup by z sum (4 - 1) and cardinality (2 - 1)
  => sums_z[3].cardinalities[1] yields a match across: index 0
  => possible solution, indexes [4,3,0]

具有适当比率约束和重量约束的背包算法

Knapsack algorithm with proper ratio constraint and weight constraint

algorithm

optimization

knapsack-problem

dynamic-programming