345. Create Maximum Number of Alloys Within Budget

Create Maximum Number of Alloys Within Budget

A company uses k machines to create alloys from n types of metals. Each machine requires a particular quantity of every metal to produce one alloy.

The composition of each machine is represented by a comma-separated string. The value at position j specifies how many units of metal type j that machine needs for one alloy.

Initially, stock.get(j) units of metal type j are available. Additional units can be purchased for cost.get(j) coins per unit.

Choose exactly one machine and use it to produce every alloy. Return the maximum number of alloys that can be created without spending more than budget coins.

Method Signature

int maxNumberOfAlloys(int n, int k, int budget, List<String> composition, List<Integer> stock, List<Integer> cost)

Parameters

n is the number of metal types.
k is the number of available machines.
budget is the maximum number of coins that may be spent.
composition.get(i) is a comma-separated string containing the metal requirements of machine i.
stock.get(j) is the available quantity of metal type j.
cost.get(j) is the cost of purchasing one unit of metal type j.

Return Value

Return the greatest number of alloys that can be produced using one machine while keeping the total purchase cost within the available budget.

Input Format Details

Every string in composition contains exactly n positive integers separated by commas.
If machine i produces x alloys, it requires x * composition[i][j] units of metal type j.
Only metal quantities exceeding the available stock need to be purchased.
Stock left after production has no additional value.

Constraints

1 <= n, k <= 100
0 <= budget <= 100,000,000
composition.size() == k
Each composition string contains exactly n values.
1 <= composition[i][j] <= 100
stock.size() == cost.size() == n
0 <= stock.get(i) <= 100,000,000
1 <= cost.get(i) <= 100

Examples

Example 1

maxNumberOfAlloys(n = 2, k = 2, budget = 10, composition = ["1,2", "2,1"], stock = [1,1], cost = [3,2])

Output: 2

Using the first machine for two alloys requires two units of the first metal and four units of the second metal. After using the available stock, the missing metals cost 1 * 3 + 3 * 2 = 9 coins. Producing three alloys with that machine exceeds the budget, and the other machine cannot produce more.

Example 2

maxNumberOfAlloys(n = 3, k = 2, budget = 12, composition = ["2,1,1", "1,3,1"], stock = [3,10,2], cost = [2,1,4])

Output: 4

The second machine can produce four alloys by purchasing one unit of the first metal, two units of the second metal, and two units of the third metal. The total cost is 1 * 2 + 2 * 1 + 2 * 4 = 12 coins. A fifth alloy cannot be produced within the budget.

Example 3

maxNumberOfAlloys(n = 2, k = 3, budget = 0, composition = ["2,2", "1,3", "4,1"], stock = [8,6], cost = [5,7])

Output: 3

No metals can be purchased because the budget is zero. The first machine can create three alloys entirely from the available stock, while each of the other machines can create at most two.