难度: Easy
Submission
运行时间: 30 ms
内存: 16.1 MB
from typing import List
class Solution:
def maxNumberOfApples(self, weight: List[int]) -> int:
weight.sort() # 按照重量从小到大排序
total_weight = 0 # 当前篮子中苹果的总重量
count = 0 # 当前篮子中苹果的数量
for w in weight:
if total_weight + w <= 5000: # 如果篮子能够放入当前苹果
total_weight += w # 将当前苹果放入篮子中
count += 1 # 苹果数量加1
else:
break # 篮子无法放入当前苹果，跳出循环
return count # 返回能够放入篮子的最大苹果数量
Explain
题解的核心思路是首先将苹果按照重量从小到大排序，然后逐个尝试将苹果放入篮子中，直到加入下一个苹果使得篮子的总重量超过5000克。这样可以确保在不超重的情况下，尽可能多地装入数量最多的苹果。此方法有效地利用了贪心算法的思想，即每次选择当前最轻的苹果，以期望最大化篮子中的苹果数量。
时间复杂度: O(n log n)
空间复杂度: O(1) — 假设排序算法为原地排序
from typing import List
class Solution:
def maxNumberOfApples(self, weight: List[int]) -> int:
weight.sort() # 将苹果按重量从小到大排序
total_weight = 0 # 初始化篮子的总重量为0
count = 0 # 初始化苹果数量为0
for w in weight:
if total_weight + w <= 5000: # 检查是否可以将当前苹果添加到篮子中而不超重
total_weight += w # 更新篮子的总重量
count += 1 # 更新篮子中的苹果数量
else:
break # 如果超重，停止添加苹果
return count # 返回篮子中的苹果总数
Explore
选择按照重量进行排序是因为问题的目标是在不超过篮子承重限制的条件下，最大化篮子中的苹果数量。通过选择最轻的苹果开始装载，可以尽可能多地装入苹果。如果按照单位重量的营养价值或其他标准排序，虽然可能从营养或价值角度优化，但不符合题目要求的最多数量的目标。
在实际应用中，苹果的重量确实存在一个自然界限，通常不会超过某个特定值（例如，一个苹果的重量很少会超过1千克）。若已知苹果重量的最大值，可用于优化算法，例如提前终止循环如果单个苹果的重量已超过篮子可承载的剩余重量。这可以提高算法的执行效率，但基本算法逻辑不变。
在此问题设定下，贪心策略（选择最轻的苹果）是保证得到最大数量苹果的有效策略。因为目标是最大化数量而非其他指标，通过从最轻的苹果开始装载，可以确保每次装载都尽可能少地占用篮子的承重空间，从而装入最多的苹果。在这种情况下，没有其他策略能够装入更多的苹果而不违背题目的限制条件。
如果承重限制改变，算法本身不需要调整，因为算法逻辑是通用的：排序后尝试添加每个苹果，直到达到承重限制。不过，承重限制的改变会直接影响最终能装入的苹果数量。承重增加会增加可装入的苹果数量，而减少则反之。算法的效率和正确性不受这些变化影响。