### PROBLEM LINK:

**Author:** Constantine Sokol

**Tester:** Mahbubul Hasan

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy

### PREREQUISITES:

Search

### PROBLEM:

Given **N** objects and **M** weighted subsets of them, find a combination of subsets, such that all objects are covered at most once and the sum of the weights are maximized.

**Some test cases are added in the practice room.**

### EXPLANATION:

Although **N** is large, **M** is quite small such that **2^M** is tolerant. Therefore, we first need to construct the conflicts between different subsets. Two subsets are called conflict if and only if they shares a common object. To get this conflicts table, on each object, we can restore the IDs of subsets who contain the object. And then, mark they are conflicted with each other. This step takes **O(N * M^2)**. Moreover, we can reduce the time complexity using the binary expression as following.

```
conflict[li] = 0;
```

[/li] For i = 1 to N do

int mask = 0;

For ID in IDs* do

mask |= 1 << ID;

end

For ID in IDs* do

conflict[ID] |= mask;

end

end

where, **conflict* >> j & 1** stands for whether the **i**-th and **j**-th subsets are conflicted with each other. This code needs only **O(NM)** time.

And then, a simple DFS search can be applied to find the maximum weighted valid choice, like following:

```
int DFS(int i, int mask, int sum)
if (i == M) {
return sum;
}
int ret = DFS(i + 1, mask, sum); // don't select the i-th subset
if (mask >> i & 1) {
// conflicted, can't be chosen.
} else {
// try to select the i-th subset
ret = max( ret, DFS(i + 1, mask | conflict*, sum + weight*);
}
return ret;
end
```

This procedure takes **O(2^M)** time. Therefore, the overall time complexity is **O(NM+2^M)**.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.