I have two list of tuples:
[[1,8],[2,7],[3,14]]
[[1,5],[2,10],[3,14]]
and a desired sum 20. I need to find two tuples from two list whose second element either add it to the sum i.e 20 or the next lowest sum. In this case if we consider [3,14] and [1,5] the sum is 14+5=19 hence the output should be [3,1]
[1,3000],[2,5000],[3,7000],[4,10000]
[1,2000],[2,3000],[3,4000],[4,5000]]
the sum is 10000. Here we have [2,5000], [4,5000] and [3,7000], [2,3000] so the output should be [2,4] and [3,2]
[[1,2000],[2,4000],[3,6000]]
[[1,2000]]
the sum is 7000. Here since I don't have a combination that sum up to 7000 I consider all the possible combinations 4000(2000+2000), 6000(4000+2000) and 8000(6000+2000) and consider the next lowest number from the desired sum which is 600. For 6000 my output should be [2,4000] and [1,2000] which is [2,1].
import itertools
def optimalUtilization(maximumOperatingTravelDistance,
forwardShippingRouteList, returnShippingRouteList):
result=[]
t1=[]
t2=[]
for miles in forwardShippingRouteList:
t1.append(miles[1])
for miles in returnShippingRouteList:
t2.append(miles[1])
result.append(t1)
result.append(t2)
total_sum=set()
for element in list(itertools.product(*result)):
if sum(element)<=maximumOperatingTravelDistance:
total_sum.add(sum(element))
total_sum=sorted(total_sum,reverse=True)
return optimalUtilizationhelper(total_sum[0],
forwardShippingRouteList, returnShippingRouteList)
def optimalUtilizationhelper(maximumOperatingTravelDistance,
forwardShippingRouteList, returnShippingRouteList):
dist_dict={}
for carid,miles in forwardShippingRouteList:
dist_dict.update({miles:carid})
result=[]
for carid,miles in returnShippingRouteList:
if (maximumOperatingTravelDistance-miles) in dist_dict:
result.append(list((dist_dict[maximumOperatingTravelDistance-miles],carid)))
return result
I get the desired result here but the complexity here is \$O(n^2 \log n)\$. What is a better way to do this?