2
$\begingroup$

If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution or a simple greedy algorithm.

A simple implementation of which could be the following. Sort the set $X$ in non-decreasing order and try taking taking the values of $X_{sorted}$ one by one only if said number is smaller than the difference of $M$ with the sum of the currently selected numbers. By the end of it we should be able to see if it is possible to form the number $M$ using a combination of that set. This will of course not work all the time.

My question is, how things would change if we knew that the numbers $w_1, w_2$ and so on are in fact guaranteed to be multiples of 2. Would then be another way to check if any given integer $M$ can be formed or not with a combination of those numbers?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Obviously, even numbers cannot add up to an odd $M$. Other than that, we could just set $v_i = w_i /2$ and $N = M/2$. Then finding a subset of $w_1, \dots w_n$ which adds up to $M$ would be the same as finding a subset of $v_1, \dots, v_n$ which adds up to $N$, where the latter is the unconstrained knapsack problem.

$\endgroup$
3
  • $\begingroup$ What advantage would dividing by 2 give me exactly? $\endgroup$
    – dearn44
    Nov 11, 2016 at 20:10
  • $\begingroup$ Dividing by 2 transforms your problem in to the usual Knapsack, showing that your problem is not easier than Knapsack. There is no practical advantage. $\endgroup$ Nov 12, 2016 at 12:10
  • $\begingroup$ This is the wrong reduction direction. $\endgroup$
    – Parham
    Sep 21, 2017 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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