Lesson 4

Programming problem.

Implement the branch-and-bound search described above. There are \(n\) stocks, and each stock may be selected at most once. For stock \(i\), the price is \(p_{i}\) and the target amount is \(t_{i}\). A selected stock contributes \(|p_{i}-t_{i}|\) to the tracking error; an unselected stock contributes \(t_{i}\).

Output two integers: the minimum tracking error found by this exact search and the number of visited search-tree nodes. The order of recursive calls, the initial value of \(\operatorname{best}\), and the pruning rule must be exactly as stated above.

• Input format.  The first line contains two integers \(1 \le n \le 60\) and \(0 \le B \le 10^{18}\). The second line contains integer prices \(1 \le p_{1},\dotsc,p_{n} \le 10^{18}\). The third line contains integer target amounts \(0 \le t_{1},\dotsc,t_{n} \le 10^{18}\). It is guaranteed that the described search visits at most \(500000\) nodes.


• Output format.  Output two integers: the minimum tracking error and the number of visited nodes.

4 18
4 6 9 11
5 5 8 10

15 25

2 6
6 6
5 5

6 5

3 20
5 7 9
0 0 0

0 1