# find vector that minimize the (W-A*B)

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?

• 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? – davidhigh Jan 10 '18 at 13:16
• Sorry I confused. Even binary tree can't – user3197493 Jan 11 '18 at 5:38