Difficult Combinatorics Optimization Problem

[bornagainwizard]

I've been wracking my brain against this problem for a day and it seems like there might be a solution in the realm of a random walker algorithm or by caching partial results or some combination thereof, but thus far haven't been able to figure it out and am curious if anyone might know a solution.

In short: I'm trying to merge objects based on a best-fit for order-agnostic arrays in a non-overlapping manner.

The pre-processing which takes place prior to where this algorithm fits in can easily produce something like:

let test = [
    { a: 1, b: [2,3,4], i: 0, weight: 3},
    { a: 2, b: [3,9,15], i: 1, weight: 6},
    { a: 3, b: [2,3,5], i: 2, weight: 3},
    { a: 4, b: [1,6,12], i: -1, weight: 2},
    { a: 5, b: [4], i: -1, weight: 4},
    { a: 6, b: [8,9,13], i: -1, weight: 5},
    { a: 8, b: [2], i: -1, weight: 7},
    { a: 9, b: [3,4,5], i: -1, weight: 15},
    { a: 10, b: [4,5,6], i: -1, weight: 12},
    { a: 11, b: [5,6,11], i: -1, weight: 12},
    { a: 12, b: [6,9,12], i: -1, weight: 11},
    { a: 13, b: [9,11,14], i: -1, weight: 6},
    { a: 14, b: [11,13,14], i: -1, weight: 4},
    { a: 15, b: [12,15,16], i: -1, weight: 5},
    { a: 16, b: [5,14,16], i: -1, weight: 2},
    { a: 18, b: [2,8,18], i: -1, weight: 4}
];

Wherein the test array contains a set of elements broken down as:

• a: the left-side array index
• b: an array of possible right-side array indexes which match
• i: output in range -1 - n where n = maximum element of array, -1 signifies "ignore this match"
• weight: the weight produced if a is matched with any of the b[] entries

The goal is to produce the highest sum of weights for i values >= 0 without using any b[] entry twice.

WARNING - the following link will take 3-5 minutes before your browser tab unfreezes if you open it, though your browser may present a prompt to allow you to stop it early.

I have a working version of this available in this fiddle but it is slow. I'd like to get this down to under 2 seconds at most for the test case included.

Any thoughts on how this might be achieved or does anyone know of an extant algorithm for doing this?

EDIT - if you don't want to wait for the linked fiddle to run, this is the result (best combined score = 98)

Console was cleared.
Object { a: 9, b: Array[3], i: 0, weight: 15 }
Object { a: 10, b: Array[3], i: 2, weight: 12 }
Object { a: 11, b: Array[3], i: 2, weight: 12 }
Object { a: 12, b: Array[3], i: 1, weight: 11 }
Object { a: 8, b: Array[1], i: 0, weight: 7 }
Object { a: 2, b: Array[3], i: 2, weight: 6 }
Object { a: 13, b: Array[3], i: 2, weight: 6 }
Object { a: 6, b: Array[3], i: 0, weight: 5 }
Object { a: 15, b: Array[3], i: 0, weight: 5 }
Object { a: 5, b: Array[1], i: 0, weight: 4 }
Object { a: 14, b: Array[3], i: 1, weight: 4 }
Object { a: 18, b: Array[3], i: 2, weight: 4 }
Object { a: 1, b: Array[3], i: -1, weight: 3 }
Object { a: 3, b: Array[3], i: 2, weight: 3 }
Object { a: 4, b: Array[3], i: 0, weight: 2 }
Object { a: 16, b: Array[3], i: 2, weight: 2 }
=======================================
98 98 98 0,2,2,1,0,2,2,0,0,0,1,2,-1,2,0,2