I want to find a candidate vector $B$ that

$$\min|(W - A_i * B_i)|$$ $$ a_i > 0,\ A_i=\{a_0,...,a_i\},\ B_i=\{-1,0,1\}^i$$

For example, given

$$W = 0.6,\quad A_4 = [0.1, 0.2, 0.4, 0.7] $$

one of answer will be

$$B_4 = [1, -1, 0, 1] $$

I only get that by searching an entire tree (DFS, BFS). I tried with a ternary tree, but 0 value in vector $B$ shuffles the ascendant order.

Dynamic-programming doesn't seem to work, divide-conquered also look at the entire tree.

What would be an efficient approach to the problem?

  • $\begingroup$ Nice question. I just don't see how it should become solvable in log-time with B in 0,1. Could you give some details on this? $\endgroup$ – davidhigh Jan 10 '18 at 13:16

Your Answer

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

Browse other questions tagged or ask your own question.