Skip to content

Instantly share code, notes, and snippets.

@czheo
Last active November 15, 2022 23:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save czheo/b5c01a35ef192713fd83d0826fe6901d to your computer and use it in GitHub Desktop.
Save czheo/b5c01a35ef192713fd83d0826fe6901d to your computer and use it in GitHub Desktop.
l1 = [23.17,3.2,1.22,0.32]
l2 = [7.36,4.16,3.20,1.69,1.28,1.28,0.96,0.96,0.90,0.64,0.64,0.64,0.50,0.50,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32,0.32]
'''
Convert input to ints because of accuracy issue with float arithmetic.
'''
l1 = [round(x * 100) for x in l1]
l2 = [round(x * 100) for x in l2]
def group(l1, l2):
def backtrack(i, ans):
if i >= len(l2):
return ans[:]
j = 0
while j < len(l1):
if l1[j] >= l2[i]:
ans.append(j)
l1[j] -= l2[i]
a = backtrack(i + 1, ans)
l1[j] += l2[i]
ans.pop()
if a:
return a
j += 1
return []
ret = {x : [] for x in l1}
if sum(l1) != sum(l2):
# No Answer
return ret
ans = backtrack(0, [])
for i, x in enumerate(ans):
ret[l1[x]].append(l2[i])
return ret
print("l1 =", l1)
print("l2 =", l2)
print("ans =", group(l1, l2))
'''
l1 = [2317, 320, 122, 32]
l2 = [736, 416, 320, 169, 128, 128, 96, 96, 90, 64, 64, 64, 50, 50, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32]
ans = {2317: [736, 416, 320, 169, 128, 128, 96, 96, 64, 64, 50, 50], 320: [64, 32, 32, 32, 32, 32, 32, 32, 32], 122: [90, 32], 32: [32]}
'''
@czheo
Copy link
Author

czheo commented Nov 15, 2022

This brute force approach will not work for reasonably larger dataset. We will need to apply further heuristics to prune the search space.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment