具有适当比率约束和重量约束的背包算法
问题: 您是一家寻找最适合您业务的供应商的果汁生产商。供应商销售含有三种成分的浓缩物:X:Y:Z,比例不同。你的果汁需要这些比例为1:1:1,否则它不会好吃。浓缩物的重量是其磅成分的总和,所有供应商都以同样的价格出售浓缩物,但是您的卡车只能携带400磅浓缩物。 寻找适合您业务的最佳供应商:购买(找到)尽可能多的磅精料(但小于400磅),知道除1:1:1之外的成分比例不可接受。具有适当比率约束和重量约束的背包算法
输入: 第一行告诉你有多少浓缩在市场上销售(小于200) 接下来n行是关于X的比例:Y:浓缩的ž成分(磅)
产量: 第一行应该是你要购买的浓缩物成分重量的总和(小于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磅的那个。
我正在寻找一种动态逼近算法,但是,我不知道如何用适当的比率约束来做到这一点。
400/3 = 133
这意味着答案可以不超过133磅的任何成分。因此DP阵列为array[134][134][134]
,其中阵列中的每个条目都是实现该组合的集中购买数量。
该数组中有大约2.4百万个条目,并且每个输入(小于200)都需要扫描一次数组。所以你在寻找大约5亿个操作来填充阵列。在现代计算机上这是合理的。
阵列填充后,一个简单的扫描找到答案
for (i = 133; i > 0; i--)
if (array[i][i][i] > 0)
the answer is array[i][i][i]
只是为了确认:例如,如果array [1] [1] [1] == 1,那么这意味着有一个组合,其中总和为3,并且有一个成分X,一个Y,一个Z?而对于数组[133] [133] [133] == 1,还有一个总数为400和133X,133Y,133Z的组合?我们从最后迭代数组,所以它可以在找到第一个答案之后停下来? – drakerc
@drakerc是的,就是这个想法。例如,如果'array [40] [29] [31]'是7,那意味着你可以购买7个包含40X,29Y和31Z的物品。如果下一个项目是2X,4Y,3Z,则另一个可达组合是'array [42] [33] [34] = 8'。但是,如果你已经有'array [42] [33] [34] == 6',那么你可以忽略新的组合,因为你试图最小化答案。数组完全填充后,您关心的唯一数组条目就是对角线上的条目,其中'X == Y == Z'。 – user3386109
非常感谢您,我会考虑实施算法来正确填充阵列,并会告诉您是否会有任何其他问题。 – drakerc
这里有可能使我们比user3386109的好主意较低的运营复杂性的方法。对三元组中的每个成员单独进行总计枚举,并为三个枚举组合中的(索引,基数)追踪匹配:对于三元组中的每个成员,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]
如果存在多个组合,该怎么办? – BlackBear
你的意思是说有两种或两种以上适当比例的组合,其成分总量的重量是相同的?这个问题并没有说明任何问题,所以我假设只会有一个这样的组合。但是,是的,会有不止一种比例适当的组合,但我们正在寻找可能含有最多成分的成分(并且所有成分为1:1:1)。 – drakerc
很有可能会有多种组合导致最好的权重,所以您需要知道是最大化还是最小化答案的第二行。 – user3386109