Most Books Within a Budget
Problem statement
A bookstore sells books only in bundles. Bundle i holds bundleQuantities[i] books and costs bundleCosts[i] dollars for the whole bundle. You can buy each bundle as many times as you like, or not at all.
You have a budget of n dollars. Return the largest total number of books you can buy without spending more than n dollars. You do not have to spend the whole budget. If no bundle fits in the budget, return 0.
Function
budgetShopping(n: int, bundleQuantities: int[], bundleCosts: int[]) → intExamples
Example 1
n = 50bundleQuantities = [20,19]bundleCosts = [24,20]return = 40Two bundles of 20 books cost 2 * 24 = 48, which fits in 50, for 40 books. Two bundles of 19 books cost 40 and give only 38 books, and a third one would cost 60. One of each costs 44 and gives 39 books. The answer is 40.
Example 2
n = 10bundleQuantities = [5,3]bundleCosts = [6,4]return = 8One 5-book bundle and one 3-book bundle cost 6 + 4 = 10 and give 8 books. Two 3-book bundles cost 8 and give only 6 books, and two 5-book bundles cost 12, which is too much. The answer is 8.
Example 3
n = 3bundleQuantities = [7,2]bundleCosts = [5,4]return = 0Every bundle costs more than the budget of 3, so you buy nothing. The answer is 0.
Constraints
1 <= n <= 10^41 <= bundleQuantities.length == bundleCosts.length <= 1001 <= bundleQuantities[i] <= 10001 <= bundleCosts[i] <= 10^4