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

Question

问题：你是一个果汁制造商，正在为你的业务寻找最好的供应商。供应商销售的浓缩液有三种成分：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的好主意。分别对三元组的每个成员执行求和枚举，并跟踪三个枚举中组合的匹配(index，cardinality(：对于三元组的每一个成员，(x,y,z)中的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 )

一旦我们对三个一维数组进行了迭代，三元组的每个成员都有一个数组，我们就可以跟踪可能的匹配。由于在所有三个枚举中跟踪一致匹配(和、基数、索引(的概率很低，因此这些情况非常罕见。

例如：

(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(中只有一个匹配(索引，基数(，然后我们可以使用相关值进行追溯：

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]