Lesson 4

Programming problem.

Implement a program for the following task. For the index-tracking problem, output the frontier of all feasible share vectors. A share vector is feasible if \(0\le a_{i}\le m_{i}\) for all \(i\) and \(\sum_{i} p_{i} a_{i}\le B\).

• Input format.  The first line contains two integers \(1 \le n \le 12\) and \(0 \le B \le 500\). The second line contains integer prices \(1 \le p_{1},\dotsc,p_{n} \le 100\). The third line contains integer target amounts \(0 \le t_{1},\dotsc,t_{n} \le 500\). The fourth line contains integer upper bounds \(0 \le m_{1},\dotsc,m_{n} \le 8\).


• Output format.  On the first line, output the number of nondominated pairs. Then output the pairs \((b,e)\), one per line, sorted by increasing \(b\).

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

7
0 28
4 24
9 21
10 20
11 19
13 17
15 15

2 6
6 6
5 5
1 1

2
0 10
6 6