Project: Portfolio Selection · Score Dynamic Programming

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Programming problem. Implement a program for the following task. There are \(n\) stocks. For stock \(i\), the price of one share is \(p_{i}\), and the score is \(r_{i}\). You may buy at most one share of each stock. Given a budget \(B\), find the maximum possible score of a portfolio whose total price is at most \(B\).

  • Input format.  The first line contains two integers \(1 \le n \le 80\) and \(1 \le B \le 1000\). The second line contains integers \(1 \le p_{1},\dotsc,p_{n} \le 100\). The third line contains integers \(1 \le r_{1},\dotsc,r_{n} \le 1000\).

  • Output format.  Output one integer: the maximum score.

5 points
Public samples
Public sample 1
Input
4 10
2 3 5 7
1 4 5 6
Expected output
10
Public sample 2
Input
3 10
6 6 10
9 9 10
Expected output
10
Public sample 3
Input
5 14
5 9 4 7 3
8 14 6 9 4
Expected output
22