Lesson 5

Programming problem.

Implement a program for the following task. There are \(n\) stocks. For stock \(i\), the price is \(p_{i}\), the target amount is \(t_{i}\), and at most \(m_{i}\) shares may be bought. Output one optimal integer share vector minimizing \[\sum_{i=1}^{n} |p_{i} a_{i}-t_{i}|\] under the budget constraint \(\sum_{i} p_{i} a_{i}\le B\).

• Input format.  The first line contains two integers \(1 \le n \le 10\) and \(0 \le B \le 120\). The second line contains integer prices \(1 \le p_{1},\dotsc,p_{n} \le 50\). The third line contains integer target amounts \(0 \le t_{1},\dotsc,t_{n} \le 200\). The fourth line contains integer upper bounds \(0 \le m_{1},\dotsc,m_{n} \le 5\).


• Output format.  Output \(n\) integers \(a_{1},\dotsc,a_{n}\). Your answer must satisfy \(0\le a_{i}\le m_{i}\) and \(\sum_{i} p_{i} a_{i}\le B\), and it must minimize the total tracking error.

4 18
4 6 9 11
5 5 8 10
2 2 2 1

0 1 0 1

2 6
6 6
5 5
1 1

0 1