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.