Algorithm to find subset of integers with highest sum under specific conditions I have a set of N>1 integers all greater than 1, not necessarily all different.
I need the most effective algorithm to find a subset of these numbers whose sum is the greatest. Unfortunately, there are some rules according to which some sets can't be chosen and verifying these rules is computationally long. Therefore I need the best way to examine the smallest number of sets and be sure to pick the set, among the allowed ones, that has the biggest sum. To be precise, what i really need is the sum itself, so if there is more than a subset that has the biggest possible sum, i don't care to have them all, I need just the value of the sum.
 - If a subset is not allowed, all of the other subset that contain it are not allowed. 
 - If a subset is allowed, all its subset are also allowed.
 - If a subset is allowed, nothing can be said about the subsets that contain it.
 - If a subset is no allowed, nothing can be said about its subset (i.e., all its subset could be allowed or some, or none)
 - All subset with 1 element are allowed.
Let's see an example. Let's say the numbers are A = 10, B = 5, C = 4, D = 1.
Let's say i find out that AB is not allowed as a set. Then also ABCD, ABC, ABD are not allowed. The highest sum that i could find is now 15, because there is at least a subset (ACD) whose sum is 15. If i check and find that ACD is allowed then i indeed found that 15 is the sum i was looking for. Otherwise, i could test BCD but its sum is only 10, like A. I still have to try AC (=14) because it can be higher than BCD. I don't have to test AD if AC is valid, because surely AD it is smaller than AC, and so on and so on...;
As you can see, there is room for some smart optimization: i need to limit as much as possible the check to see if a given subset is valid (calculating the sum is, of course, just a sum and is not computationally important).
I think i am not the first one that needs such an algorithm but i couldnt find anything online.
Thanks
Wentu
 A: One way I can think of is to use Boolean algebra.
For example, given $A=10, B=5, C=4, D=1, E=1, F=2, G=7$ with $AB, DG,$ and $AG$ disallowed:
We can say that our disallowed combinations look like $(AB + DG + AG)'$. ($XY$ means $X \text{ and } Y$. $X + Y$ means $X \text{ or } Y$. $X'$ means $\text{not } X$.)
Applying de Morgan's Law and distributing when necessary:
$$\begin{align}
& (AB + DG + AG)'\\
& (AB)'(DG)'(AG)'\\
& (A' + B')(D' + G')(A' + G')\\
& (A'D' + A'G' + B'D' + B'G')(A' + G')\\
& A'D' + A'D'G' + A'G' + A'B'D' + B'D'G' + A'B'G' + B'G'\\
& A'D'(1 + G' + B') + A'G' + B'D'G' + A'B'G' + B'G\\
& A'D' + G'(A' + B'D' + A'B' + B')\\
& A'D' + G'(A' + B'(D' + A' + 1))\\
& A'D' + G'(A' + B')\\
& A'D' + A'G' + B'G'
\end{align}$$
In other words, you can discard either $AD, AG,$ or $BG$.
$A+D=11;\quad A+G=17;\quad B+G=12$
So it looks like you can discard $AD$ with the least impact to the overall sum. Discarding $A$ and $D$ leaves you with $B, C, E, F,$ and $G$.
$B+C+E+F+G = 5 + 4 + 1 + 2 + 7 = 19$. So $19$ is the maximum sum in this example.
A: Do you have an idea of your values ?
N is 100, 1000, 10000 ?
Imagine you test all subsets with 2 integers, which proportion of them will be allowed ?  20% or 99% ?
Imagine you test all subsets with 10 integers, which proportion of them will be allowed ?  5% or 50% ?
If the proportion of subsets which are allowed is known by advance (not exact value, just an approximate value), I am pretty sure it can help.
