I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset of {2,7,11} which has elements that sum to 13. Here is the algorithm for solving this:
In binary notation 2=0010, 7=0111, 11=1011, 13=1101. Suppose that 2x+7y+11z=13, where x,y,z are {0,1}.
Then y+z=1 (mod 2), since the last bits of 7, 11, and 13 are 1 and the last bit of 2 is 0.
And (y+z-1)+2*(x+y+z)=0 (mod 4), since the second to last bits of 2, 7, and 11 are 1 and the second to last bit of 13 is 0. (The y+z-1 is the carry bit from before.)
And ((y+z-1)+2*(x+y+z)-0)+4y=4 (mod 8), since the third to last bits of 7 and 13 are 1 and the third to last bit of 2 and 11 are 0. (The (y+z-1)+2*(x+y+z)-0 is the carry bit from before.)
And finally ((y+z-1)+2*(x+y+z)-0)+4y-4)+8z=8 (mod 16), since the first bits of 11 and 13 are 1 and the first bit of 2 and 7 are 0. (The ((y+z-1)+2*(x+y+z)-0)+4y-4 is the carry bit from before.)
So we have four linear equations over a finite ring, if we change each one to mod 16.
8y+8z=8 (mod 16)
8x+12y+12z=4 (mod 16)
4x+14y+6z=10 (mod 16)
2x+7y+11z=13 (mod 16)
As we can see, a solution is x=1, y=0, z=1, as one would expect, since the set {2,11} has elements that sum to 13. We could have gotten this through Gaussian elimination (according to answers to my last question on this site).
By request, here is the general algorithm that I just wrote (which can be induced from the above example): We want to solve a_1*x_1 + ... a_n*x_n = b, where each a_j and b is an integer and each x_j is in {0,1}. Putting each a_j and b in binary, we have a_j=(a_{mj} ... a_{1j}) and b=(b_m ... b_1), for suitable m. For instance, a_j=5 in binary is (a_{4j} ... a_{1j})=(0 1 0 1) - highest bit on the left side, lowest on the right side.
Here is the simple algorithm for constructing a new matrix A=(a_{ij}) from this original (a_{ij}) and a new b=(b_i) from this original b:
`Let b_1 = 2^{m-1}*b_1; For j=1 to n Let a_{1j} = 2^{m-1}*a_{1j};
For i=2 to m { Let b_i = 2^{m-1}*b_i + b_{i-1}/2; For j=1 to n Let a_{ij} = 2^{m-1}*a_{ij} + a_{(i-1),j}/2; }`
Next solve the matrix equation Ax=b (mod 2^m), for the new A=(a_{ij}) and b=(b_i). If there is a solution to the knapsack problem, there should be a solution for x in {0,1} in Ax=b (mod 2^m) and vice versa (since the last row is just the original a_j and b). I'm curious to see if it works for large m and n. Anyone want to give it a shot?
What's wrong with this approach? It shouldn't work, but I don't know why.