In your shoes, the way I would tackle this problem is first find a UKP solution for less than or equal to the target weight. Call this solution1. If solution1 equal to the target, then you are done. Otherwise, solve for the UKP's of target + 1 to 2 * target - solution1 - 1. When you get a solution that is less than abs(target - solution1) then you have your answer. If you can't find a solution less than abs(target - solution1), then solution1 is (one of) the best answer(s) you can get.