目录
一、零钱兑换
1.1 思路一：动态规划
1.2 思路二：贪心
二、安排工作以达到最大效益
2.1 具体思路
2.2 思路呈现
2.3 代码实现
2.4 复杂度分析
2.5 运行结果
三、雇佣k名工人的最低成本
3.1 具体思路
3.2 思路展示
3.3 代码实现
3.4 复杂度分析
3.5 运行结果
结尾语
“生活有意思的点就在于未知的某些时刻，你准备去a的时候，可能会遇到b，聊到c，想到d，然后一起去找了e”
一、零钱兑换
力扣第322题
1.1 思路一：动态规划
（1）具体思路
首先初始化一个长度为 amount+1 的数组 dp，dp[i] 表示凑齐金额 i 需要的最少硬币数，初始值为 amount+1，因为最多只需要凑齐 amount 枚 1 元硬币。
将 dp[0] 初始化为 0，表示凑齐金额 0 不需要任何硬币。
对于每个金额 i，遍历硬币数组 coins，如果当前硬币面额 j 小于等于 i，更新 dp[i] = min(dp[i], dp[i - j] + 1)。
最终返回 dp[amount]，如果 dp[amount] 大于 amount，则表示无法凑齐总金额，返回 -1。
（2）思路呈现
假设有三种硬币，面额分别为 1、2、5 元，我们要凑齐总金额为 11 元。按照动态规划的思路，我们可以进行如下步骤：
初始化一个长度为 12（amount+1）的数组 dp，并将所有元素初始化为正无穷大，表示初始时无法凑出任何金额。
dp = [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
将 dp[0] 初始化为 0，表示凑齐金额 0 不需要任何硬币。
dp[0] = 0
对于每个金额 i，遍历硬币数组 coins，如果当前硬币面额 j 小于等于 i，更新 dp[i] = min(dp[i], dp[i - j] + 1)。
遍历到金额 1：
当前硬币面额为 1，小于等于 1，更新 dp[1] = min(inf, dp[1-1]+1) = min(inf, dp[0]+1) = min(inf, 0+1) = 1
遍历到金额 2：
当前硬币面额为 1，小于等于 2，更新 dp[2] = min(1, dp[2-1]+1) = min(1, dp[1]+1) = min(1, 1+1) = 1
当前硬币面额为 2，小于等于 2，更新 dp[2] = min(1, dp[2-2]+1) = min(1, dp[0]+1) = min(1, 0+1) = 1
遍历到金额 3：
当前硬币面额为 1，小于等于 3，更新 dp[3] = min(1, dp[3-1]+1) = min(1, dp[2]+1) = min(1, 1+1) = 1
当前硬币面额为 2，小于等于 3，更新 dp[3] = min(1, dp[3-2]+1) = min(1, dp[1]+1) = min(1, 1+1) = 1
...以此类推
最终返回 dp[11]，如果 dp[11] 大于 11，则表示无法凑齐总金额，返回 -1。
dp[11] = 3 （表示凑齐金额 11 需要的最少硬币数）
因此，对于硬币面额为 [1, 2, 5]，要凑齐金额 11，最少需要 3 枚硬币。
（3）代码实现
def coinChange(coins, amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] <= amount else -1
# 示例测试
print(coinChange([1, 2, 5], 11)) # 输出：3
print(coinChange([2], 3)) # 输出：-1
print(coinChange([1], 0)) # 输出：0（4）复杂度分析
时间复杂度分析：
外层循环对每个金额 i 进行遍历，内层循环对每个硬币进行遍历，所以总的时间复杂度为 O(n * k)，其中 n 为金额数，k 为硬币种类数。
空间复杂度分析：
代码中使用了一个长度为 amount+1 的数组 dp 作为动态规划的辅助空间，因此空间复杂度为 O(amount)。
综合来看，这段代码的时间复杂度为 O(n * k)，空间复杂度为 O(amount)。
1.2 思路二：贪心
（1）具体思路
将硬币数组 coins 按照面额从大到小排序，这样可以保证每次选择的硬币面额尽可能大，尽量减少硬币数量。
定义一个变量 count，表示凑成总金额所需的最少硬币个数，初始化为 0。
遍历排序后的硬币数组 coins，对于每个硬币面额 coin，尽可能地使用多个硬币，直到凑够总金额 amount 或者不能再继续添加硬币为止。
如果凑够了总金额 amount，则返回 count；否则返回 -1。
（2）思路呈现
假设硬币数组 coins = [1, 2, 5]，总金额 amount = 11。
首先，将硬币数组按照面额从大到小排序，得到 [5, 2, 1]。
初始化 count = 0。
开始遍历排序后的硬币数组。
当遍历到硬币面额为 5 时，我们可以使用两个硬币 5，凑够了总金额 11，此时 count = 2。返回 count。
下面是对应的示意图：
coins = [5, 2, 1]
amount = 11
count = 0
返回 count = 2
（3）代码实现
def coinChange(coins, amount):
# 将硬币数组按照面额从大到小排序
coins.sort(reverse=True)
# 定义一个变量 count，表示凑成总金额所需的最少硬币个数
count = 0
# 遍历硬币数组，对于每个硬币面额 coin，尽可能地使用多个硬币
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
# 如果凑够了总金额 amount，则返回 count；否则返回 -1
return count if amount == 0 else -1
# 示例测试
print(coinChange([1, 2, 5], 11)) # 输出：3
print(coinChange([2], 3)) # 输出：-1
print(coinChange([1], 0)) # 输出：0（4）复杂度分析
①时间复杂度分析：
对硬币数组进行排序的时间复杂度为 O(n log n)，其中 n 为硬币种类数。
遍历排序后的硬币数组需要 O(n) 的时间，每次遍历的时间复杂度为 O(amount/coin)，其中 coin 表示当前硬币的面额。
因此，总的时间复杂度为 O(n log n + n * amount/coin_max)，其中 coin_max 表示硬币数组中面额最大的硬币。
②空间复杂度分析：
这段代码只使用了常数级别的额外空间，所以空间复杂度为 O(1)。
这段代码的时间复杂度主要取决于排序操作的时间复杂度，为 O(n log n)。
空间复杂度为 O(1)，非常低。
需要注意的是，这个算法使用了贪心策略，可能无法得到最优解。在某些情况下，可能会出现无法凑够总金额的情况，返回 -1。如果需要求得准确的最少硬币个数，可以考虑使用动态规划等其他算法。
（5）运行结果
三个示例如下
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
结果均与预期一致
二、安排工作以达到最大效益
力扣826题
本题采用贪心的思想解决
2.1 具体思路
首先，我们需要将工作按照难度从小到大进行排序，并且保持与对应的收益的对应关系。可以使用zip函数将难度数组和收益数组合并，并根据难度进行排序。
接下来，我们需要对工人的能力数组进行排序，以便之后逐个遍历工人。
初始化总收益为0，并设置两个指针：一个指向工人能力数组的当前工人，一个指向工作数组的当前工作。
开始遍历工人能力数组，对于每个工人能力，我们需要找到他能够完成的难度范围内的最高收益。
在遍历工作数组时，如果当前工作的难度小于等于当前工人的能力，更新最高收益为当前工作的收益。然后，移动工作指针以处理下一个工作。
如果当前工作的难度大于当前工人的能力，或者已经遍历完所有工作，则将当前工人的最高收益加到总收益中，并继续处理下一个工人。
最后，返回总收益作为结果。
2.2 思路呈现
假设有四个工作，难度和收益分别如下：
难度：[2, 4, 6, 8]
收益：[10, 20, 30, 40]
现在有三个工人，能力数组如下：
[4, 5, 6]
首先，我们将工作按照难度从小到大进行排序，同时保持与对应的收益的对应关系：
难度：[2, 4, 6, 8]
收益：[10, 20, 30, 40]
接下来，对工人的能力数组进行排序：
工人能力：[4, 5, 6]
初始化总收益为0，并设置两个指针，一个指向工人能力数组的当前工人，一个指向工作数组的当前工作。
开始遍历工人能力数组，对于每个工人能力，我们需要找到他能够完成的难度范围内的最高收益。
对于第一个工人，能力为4。遍历工作数组，发现第一个工作的难度2小于等于4，更新最高收益为10。继续遍历，发现第二个工作的难度4也小于等于4，但是收益20比已经记录的最高收益10要低，所以最高收益仍然是10。继续遍历，发现第三个工作的难度6大于4，结束遍历。将最高收益10加到总收益中。
对于第二个工人，能力为5。遍历工作数组，发现第一个工作的难度2小于等于5，更新最高收益为10。继续遍历，发现第二个工作的难度4也小于等于5，更新最高收益为20。继续遍历，发现第三个工作的难度6大于5，结束遍历。将最高收益20加到总收益中。
对于第三个工人，能力为6。遍历工作数组，发现第一个工作的难度2小于等于6，更新最高收益为10。继续遍历，发现第二个工作的难度4也小于等于6，更新最高收益为20。继续遍历，发现第三个工作的难度6等于6，更新最高收益为30。继续遍历，发现第四个工作的难度8大于6，结束遍历。将最高收益30加到总收益中。
最后，返回总收益作为结果。根据上述计算，总收益为10 + 20 + 30 = 60。
2.3 代码实现
def maxProfitAssignment(difficulty, profit, worker):
# 将难度和对应的收益按照难度升序进行排序
jobs = sorted(zip(difficulty, profit))
# 对工人的能力进行排序
worker.sort()
total_profit = 0
i = 0
max_profit = 0
for ability in worker:
while i < len(jobs) and ability >= jobs[i][0]:
# 更新当前能力范围内的最大收益
max_profit = max(max_profit, jobs[i][1])
i += 1
total_profit += max_profit
return total_profit
# 示例测试
print(maxProfitAssignment([2, 4, 6, 8, 10], [10, 20, 30, 40, 50], [4, 5, 6, 7])) # 输出：100
print(maxProfitAssignment([85, 47, 57], [24, 66, 99], [40, 25, 25])) # 输出：02.4 复杂度分析
首先，对难度和收益进行排序，时间复杂度为O(nlogn)，其中n为工作的数量。
对工人的能力进行排序，时间复杂度为O(mlogm)，其中m为工人的数量。
遍历工人能力数组，对于每个工人能力，在内部循环中遍历工作数组，直到找到工人能力范围内的最高收益。由于工作数组已经按照难度升序排列，因此在内部循环中只需要从上一次结束的位置开始遍历即可，避免了不必要的遍历。因此，内部循环的时间复杂度为O(n)，其中n为工作的数量。
综上所述，总的时间复杂度为O(nlogn + mlogm + n)，也可以简化为O(max(nlogn, mlogm))。空间复杂度为O(1)，没有使用额外的空间。
2.5 运行结果
I示例及预期结果如下
示例 1：
输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。
示例 2:
输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0
II 实际输出与预期结果一致
三、雇佣k名工人的最低成本
力扣第857题
本题依旧使用贪心的思想，具体分析如下
3.1 具体思路
首先，我们可以计算工人的“性价比”，即 wage[i]/quality[i]，表示每单位工作质量所需的工资。
然后，我们对所有工人按照性价比进行排序，并依次计算以当前工人为基准的工资组的总工资。具体步骤如下：
①首先，我们对工人按照性价比进行排序。
②然后，从性价比最小的工人开始，依次计算以当前工人为基准的工资组的总工资。具体做法是，对于当前工人，我们以他的性价比作为标准，计算出其他工人的期望工资，然后将这些期望工资按照工作质量排序。取前k-1 个工人的期望工资之和，加上当前工人的期望工资，就得到了以当前工人为基准的工资组的总工资。
③我们遍历所有工人，不断更新最小的总工资。
3.2 思路展示
假设有5名工人，他们的工作质量和最低期望工资分别如下：
quality = [3, 1, 10, 10, 1]
wage = [4, 8, 2, 2, 7]
首先，我们计算每名工人的性价比，即 wage[i]/quality[i]，得到以下结果：
性价比 = [4/3, 8/1, 2/10, 2/10, 7/1] = [1.33333, 8, 0.2, 0.2, 7]
按照性价比进行排序，得到以下顺序：
性价比排序 = [0.2, 0.2, 1.33333, 7, 8]
现在从性价比最小的工人开始，依次计算以当前工人为基准的工资组的总工资。
以第一个工人（性价比为0.2）为基准，计算其他工人的期望工资并按工作质量排序：
期望工资 = [0.2 * 3, 0.2 * 1, 0.2 * 10, 0.2 * 10, 0.2 * 1] = [0.6, 0.2, 2, 2, 0.2]
按工作质量排序后为：[0.2, 0.2, 0.6, 2, 2]
取前k-1个工人的期望工资之和，加上当前工人的期望工资，得到以当前工人为基准的工资组的总工资：
总工资 = 0.2 + 0.2 + 0.6 = 1
接下来，以第二个工人（性价比为0.2）为基准重复以上步骤：
期望工资 = [0.2 * 3, 0.2 * 1, 0.2 * 10, 0.2 * 10, 0.2 * 1] = [0.6, 0.2, 2, 2, 0.2]
按工作质量排序后为：[0.2, 0.2, 0.6, 2, 2]
总工资 = 0.2 + 0.2 + 0.6 = 1
以此类推，最后得到总工资最小的工资组。
3.3 代码实现
import heapq
def mincostToHireWorkers(quality, wage, k):
n = len(quality)
workers = sorted((w / q, q, w) for w, q in zip(wage, quality))
ans = float('inf')
pool = []
sumq = 0
for ratio, q, w in workers:
heapq.heappush(pool, -q)
sumq += q
if len(pool) > k:
sumq += heapq.heappop(pool)
if len(pool) == k:
ans = min(ans, sumq * ratio)
return ans
# 示例测试
print(mincostToHireWorkers([10,20,5], [70,50,30], 2)) # 输出：105.00000
print(mincostToHireWorkers([3,1,10,10,1], [4,8,2,2,7], 3)) # 输出：30.666673.4 复杂度分析
该算法的时间复杂度为 O(nlogn)，其中 n 为工人数量。主要是因为对工人进行排序所需的时间复杂度为 O(nlogn)。
空间复杂度为 O(n)，主要是因为要存储每名工人的性价比、工作质量和期望工资，以及维护一个大小为 k 的小根堆。
在算法实现中，使用了 heapq 模块来快速实现小根堆的维护，从而使代码更加简洁高效。
3.5 运行结果
示例测试如下
运行结果如下，与预期一致
结尾语
“生活有意思的点就在于未知的某些时刻，你准备去a的时候，可能会遇到b，聊到c，想到d，然后一起去找了e”
祝你天天开心！文章来源：https://www.toymoban.com/news/detail-827850.html
2024-2-2文章来源地址https://www.toymoban.com/news/detail-827850.html
到了这里，关于算法设计与分析实验：动态规划与贪心的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
