1
$\begingroup$

I want find candidate of B vector 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$$ $$A_4 = [0.1, 0.2, 0.4, 0.7] $$ one of answer will $$B_4 = [1, -1, 0, 1] $$

I only get way that search every tree (DFS, BFS).

I tried with ternary tree, but 0 value in vector B suffle ascendant order.

Dynamic-programming doesnt' work, divide-conquered also look every tree.

any solution?

$\endgroup$
  • $\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
  • $\begingroup$ Sorry I confused. Even binary tree can't $\endgroup$ – user3197493 Jan 11 '18 at 5:38

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.