2861. Maximum Number of Alloys Medium

1/**
2 * [2861] Maximum Number of Alloys
3 *
4 * You are the owner of a company that creates alloys using various types of metals. There are n different types of metals available, and you have access to k machines that can be used to create alloys. Each machine requires a specific amount of each metal type to create an alloy.
5 * For the i^th machine to create an alloy, it needs composition[i][j] units of metal of type j. Initially, you have stock[i] units of metal type i, and purchasing one unit of metal type i costs cost[i] coins.
6 * Given integers n, k, budget, a 1-indexed 2D array composition, and 1-indexed arrays stock and cost, your goal is to maximize the number of alloys the company can create while staying within the budget of budget coins.
7 * All alloys must be created with the same machine.
8 * Return the maximum number of alloys that the company can create.
9 *  
10 * <strong class="example">Example 1:
11 * 
12 * Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
13 * Output: 2
14 * Explanation: It is optimal to use the 1^st machine to create alloys.
15 * To create 2 alloys we need to buy the:
16 * - 2 units of metal of the 1^st type.
17 * - 2 units of metal of the 2^nd type.
18 * - 2 units of metal of the 3^rd type.
19 * In total, we need 2 * 1 + 2 * 2 + 2 * 3 = 12 coins, which is smaller than or equal to budget = 15.
20 * Notice that we have 0 units of metal of each type and we have to buy all the required units of metal.
21 * It can be proven that we can create at most 2 alloys.
22 * 
23 * <strong class="example">Example 2:
24 * 
25 * Input: n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3]
26 * Output: 5
27 * Explanation: It is optimal to use the 2^nd machine to create alloys.
28 * To create 5 alloys we need to buy:
29 * - 5 units of metal of the 1^st type.
30 * - 5 units of metal of the 2^nd type.
31 * - 0 units of metal of the 3^rd type.
32 * In total, we need 5 * 1 + 5 * 2 + 0 * 3 = 15 coins, which is smaller than or equal to budget = 15.
33 * It can be proven that we can create at most 5 alloys.
34 * 
35 * <strong class="example">Example 3:
36 * 
37 * Input: n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
38 * Output: 2
39 * Explanation: It is optimal to use the 3^rd machine to create alloys.
40 * To create 2 alloys we need to buy the:
41 * - 1 unit of metal of the 1^st type.
42 * - 1 unit of metal of the 2^nd type.
43 * In total, we need 1 * 5 + 1 * 5 = 10 coins, which is smaller than or equal to budget = 10.
44 * It can be proven that we can create at most 2 alloys.
45 * 
46 *  
47 * Constraints:
48 * 
49 * 	1 <= n, k <= 100
50 * 	0 <= budget <= 10^8
51 * 	composition.length == k
52 * 	composition[i].length == n
53 * 	1 <= composition[i][j] <= 100
54 * 	stock.length == cost.length == n
55 * 	0 <= stock[i] <= 10^8
56 * 	1 <= cost[i] <= 100
57 * 
58 */
59pub struct Solution {}
60
61// problem: https://leetcode.com/problems/maximum-number-of-alloys/
62// discuss: https://leetcode.com/problems/maximum-number-of-alloys/discuss/?currentPage=1&orderBy=most_votes&query=
63
64// submission codes start here
65
66impl Solution {
67    pub fn max_number_of_alloys(n: i32, k: i32, budget: i32, composition: Vec<Vec<i32>>, stock: Vec<i32>, cost: Vec<i32>) -> i32 {
68        0
69    }
70}
71
72// submission codes end
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_2861() {
80    }
81}
82