Lesson 2

For optimization, replace counts by best scores. Let \(K_{i}(b)\) be the maximum score of a portfolio that uses only the first \(i\) stocks and has total price exactly \(b\). If no such portfolio exists, set \(K_{i}(b)=-\infty\). The initial values are \(K_{0}(0)=0\) and \(K_{0}(b)=-\infty\) for \(b>0\). Then, \[K_{i}(b)=\max\left(K_{i-1}(b),K_{i-1}(b-p_{i})+r_{i}\right).\] If \(b<p_{i}\) or \(K_{i-1}(b-p_{i})=-\infty\), the second term is ignored. The answer under budget \(B\) is \(\max_{0\le b\le B}K_{n}(b)\). This is the standard knapsack dynamic program.