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$
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$
  • $\begingroup$ What advantage would dividing by 2 give me exactly? $\endgroup$ – dearn44 Nov 11 '16 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$ – Karolis Juodelė Nov 12 '16 at 12:10
  • $\begingroup$ This is the wrong reduction direction. $\endgroup$ – Parham Sep 21 '17 at 12:52

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.