Select Weighted Items From List with Restrictions

Question

I have a list of weights where each index represents the weight of an item.

Weights = [0.3, 0.7, 0.1, 0.3, 0.1, ...]

Each item has a list of of collision items, hence if you pick item 0 you can't pick item 1.

Item_0 = [0,1,3,7]
Item_1 = [1,5,6,8]

All the items have the same number of collisions.

The goal is to pick N items keeping in mind the collisions and maximize the weight of the items picked.

What's the easiest and most pythonic way to do this?

I initially thought a greedy approach will work (sort the weights in descending order) but it doesn't and the only other solution I can come up with is finding all possible combinations of N items (without collisions) and calculating the total weights.

Greedy Algorithm (Gives incorrect result):

def pickTop_K(weights, collision_dict):
    ret = []

    while len(ret) < k:

        index = np.argmax(probs)
        ret.append(index)

        collisions = collision_dict[index]
        weights[collisions] = 0

        if np.max(weights) == 0:
            break

    return ret

Yes, all the elements have the same number of collisions. I've edited the question as well. — S. Salman
I believe this problem to be connected with the maximum weighted independent set: wincent.com/wiki/… — Dani Mesejo
So for item 0, you cant pick items 0, 1, 3 and 7? I'm just clarifying. Also are the items just indices of Weights? So item 0 -> 0.3, item 1 -> 0.7 etc. — RoadRunner
nice problem description ...where is the code that tries to solve it and what is the specific problem with it? Can you post an exaustive set of items/weights (or limit the one you have to a short list? — Patrick Artner
So for item 0, after we pick 0, we can't pick 0, 1, 3 and 7. Yes. And yes the items are just indices of the weights. The problem is that a solution that comes up with the optimal solution would be too computationally unfeasible according to me. I'll add the code for the greedy solution I came up with which I realized wasn't optimal. — S. Salman

btilly btilly · Accepted Answer · 2020-08-29T21:24:32

I'm fairly sure that this problem is NP-hard.

However there is a way to solve it while limiting how much work you do as follows.

First, sort the vertices by descending weight.

Then do an A* search. That is, you have a priority queue that always returns the highest priority option. The priority of a set of choices is the total weight of the choices plus an upper bound on the weight of choosing the next few vertices.

In pseudocode that looks something like this.

create priority queue paths
add to paths an empty set with weight the sum of the first n items.
while paths is not empty:
    take the top path from the queue.
    If the path is a set of n choices:
        that is your answer, return it
    else:
        Look for the next element that could or couldn't be added.
        If you found it:
            Add an option to the queue where you choose it
            Add an option to the queue where you don't choose it
        Else:
            This is a dead end.  Pass.

My best guess is that it is probably worthwhile to make the best estimate that you can of the upper limit. That is, you actually find the top vertices that are not in conflict with any existing choice and sum them to come up with a good upper bound. This operation is expensive, but reduces branching. And the exponential growth in options comes from branching - it is worth investment to prune branches early.

If the greedy choice works, this algorithm will find it very quickly. If something close to the greedy choice works, there shouldn't be too much backtracking. But if you're unlucky, this will take exponential space and memory. (But if it is actually NP-hard, you can't expect to do better than that.)

Select Weighted Items From List with Restrictions

1 Answers