0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.