Bottom-up algorithm to build subset of maximum weight I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R of size n: for each j in R[i] we have that  the subset can not contain both P[i] and P[j].
How do I build a DP bottom-up solution for this problem?
This is the maximum-weight independent set problem, which is known to be NP-hard.  Therefore, there is unlikely to be any efficient solution. However, you could use any of the standard algorithms for this problem, if you're willing to accept an exponential-time algorithm.