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

问题：您是一家寻找最适合您业务的供应商的果汁生产商。供应商销售含有三种成分的浓缩物：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磅的那个。

我正在寻找一种动态逼近算法，但是，我不知道如何用适当的比率约束来做到这一点。

来源

2016-11-08 drakerc

如果存在多个组合，该怎么办？ – BlackBear

你的意思是说有两种或两种以上适当比例的组合，其成分总量的重量是相同的？这个问题并没有说明任何问题，所以我假设只会有一个这样的组合。但是，是的，会有不止一种比例适当的组合，但我们正在寻找可能含有最多成分的成分（并且所有成分为1：1：1）。 – drakerc

很有可能会有多种组合导致最好的权重，所以您需要知道是最大化还是最小化答案的第二行。 – user3386109

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]

来源

2016-11-08 20:57:51 user3386109

只是为了确认：例如，如果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]

来源

2016-11-11 05:30:24

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

回答

相关问题