For this problem, you may think about part a, as well as look at my solution, but no need to talk about it, only part b.

You have a budget of B dollars and want to buy as many books as possible from a bookstore.
The bookstore offers n different types of books, each priced at p1, p2,..., pn dollars. You may
assume all the costs are positive so pi > 0 for every i.

(a) Using the template laid out at the beginning of this document, describe a dynamic programming algorithm that determines the maximum number of books you can purchase
while spending all of your money. If it is not possible to spend all of the B dollars, the
algorithm should return “Impossible”.
For example, if there are two types of books priced p1 = 2 and p2 = 5, and you have a
budget of B = 9 dollars, you can buy a maximum of three books, one of the second type
and two of the first type. If, on the other hand, B = 3, your algorithm should return
“Impossible”.
(b) Give an algorithm to recover the actual optimal solution (if it exists), i.e., the number
of books of each type that you buy so as to maximize the total number of books while
spending all of your money. Your answer should include both pseudocode and a brief
description in English. Analyze and derive the asymptotic running time of your algorithm

My solution to part a:

2)
a)
English Description:

Subproblem: Define an array maxBooks[0 … budget] where maxBooks[x] represents the maximum number of books that can be bought with a total cost of exactly x. Each subproblem corresponds to finding the maximum number of books that can be purchased for each possible total cost up to the budget.

Recurrence:

For each total cost from 1 to the budget:
Consider each type of book:
If the price of the current book does not exceed the current total cost and the remaining total cost is achievable (i.e., a solution exists for maxBooks[totalCost - price[bookIndex]]), then update the maximum number of books for the current total cost.

Logic Behind Recurrence: For each total cost up to the budget, we iterate through each book type. If we can afford the current book (totalCost >= price[bookIndex]) and it's possible to reach the remaining cost after buying it (maxBooks[totalCost - price[bookIndex]] != -1), we consider buying it. We then update maxBooks[totalCost] with the maximum between its current value and maxBooks[totalCost - price[bookIndex]] + 1, where the +1 represents adding the current book to the solution.

Recurrence and Base Case:

Base Case: maxBooks[0] = 0 (we can buy 0 books with $0).

Recurrence Relation:

For totalCost from 1 to budget:
maxBooks[totalCost] = -1 (initialize as impossible)

For totalCost from 1 to budget:
For bookIndex from 1 to n:
If ( totalCost >= price[bookIndex] & maxBooks[totalCost - price[bookIndex]] != -1):
maxBooks[totalCost] = max(maxBooks[totalCost], maxBooks[totalCost - price[bookIndex]] + 1)

Final Value to Return:

If maxBooks[budget] != -1: return maxBooks[budget] (return the maximum number of books if a solution exists for the given budget)
Else: return “Impossible” (return "Impossible" if it's not possible to reach the exact budget with the given book prices)

Pseudocode:

maxBooks(budget, price[1, …, n]):

// Initialize maxBooks to -1

For totalCost from 0 to budget:
	maxBooks[totalCost] = -1
maxBooks[0] = 0 // base case
		
For totalCost from 1 to budget:
	For bookIndex from 1 to n:
		If totalCost >= price[bookIndex] & maxBooks[totalCost - price[bookIndex]] != -1:
					
			maxBooks[totalCost] = max(maxBooks[totalCost], maxBooks[totalCost - price[bookIndex]] + 1)


If maxBooks[budget] != -1:
	Return maxBooks[budget]
Else:
	Return “Impossible”
Algorithm Runtime Analysis:

Outer loop (totalCost): O(budget)
Inner loop (bookIndex): O(n)
Therefore overall = O(budget * n) = O(n * budget)