难度: Medium
Submission
运行时间: 205 ms
内存: 57.4 MB
class Solution:
def maxPrice(self, items: List[List[int]], capacity: int) -> float:
# 用单位质量的价值来排序
def sort_key(x):
return -x[0] / x[1]
n = len(items)
total = 0
for x in items:
total += x[1]
if total < capacity:
return -1
items = sorted(items, key = sort_key)
#print(items)
price = 0
for x in items:
if x[1] > capacity:
price += x[0] * capacity / x[1]
break
else:
price += x[0]
capacity -= x[1]
return price
Explain
这个题解采用了贪心算法的思想。首先定义一个辅助函数 sort_key 来计算每个物品的单位质量的价值（价格除以重量），并按照这个价值从高到低进行排序。然后检查所有物品的总重量是否小于背包容量，如果小于则直接返回 -1 表示无法填满背包。接下来遍历排序后的物品列表，优先选择单位价值高的物品加入背包，如果当前物品的重量超过了剩余的背包容量，则按照其单位价值取相应比例的物品填满背包，计算对应的价格，并结束循环。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def maxPrice(self, items: List[List[int]], capacity: int) -> float:
# 定义排序键，按照单位价格从高到低排序
def sort_key(x):
return -x[0] / x[1]
# 计算所有物品的总重量
total = sum(x[1] for x in items)
# 如果物品总重量小于背包容量，返回-1表示无法填满
if total < capacity:
return -1
# 对物品按单位价值进行排序
items = sorted(items, key=sort_key)
# 初始化总价格为0
price = 0
# 遍历物品，尽量填充背包
for x in items:
if x[1] > capacity:
# 如果当前物品重量超过剩余容量，按比例计算价格并结束
price += x[0] * capacity / x[1]
break
else:
# 否则，完全使用当前物品，并减少对应的容量
price += x[0]
capacity -= x[1]
return price
Explore
在这个算法中，返回 -1 是因为我们的目标是完全填满背包。如果所有可用的物品的总重量还没有达到背包的容量，那么就无法实现目标，因此直接返回 -1 表示无法解决问题。这里的场景确实是指背包必须被完全填满，这可能是为了满足某些特定的实际需求，如确保物资的最大化利用或其他条件。
使用单位价值作为排序依据的方法主要是基于贪心算法，它在一些情况下可能不会得到最优解。特别是在物品不能被分割或者每种物品的数量有限的情况下，简单地按单位价值排序并选择可能会导致背包容量用不满，从而无法达到可能的最大总价值。此外，如果问题要求的不仅仅是最大化价值，还包括其他考量（如最小化物品数量或满足特定物品组合的需求），单纯的贪心策略也可能不适用。
在贪心算法的框架下，如果遇到连续几个物品的重量超过剩余容量，算法会尝试按比例取用这些物品的一部分以最大化价值。然而，这种做法仍然依赖于物品可以被分割这一假设。如果物品不可分割，这种情况下贪心算法可能就不再适用，而需要采用动态规划等其他算法来确保找到最优解。动态规划可以考虑多种组合和分割情况，从而在整体上找到价值最大化的解决方案。
在不改变物品原始顺序的情况下解决问题通常会涉及不同的算法设计，如动态规划。这种方法不依赖于物品的排序，而是通过构建一个决策矩阵来考虑每种可能的物品组合。这样可以在不改变物品顺序的前提下，根据背包的容量逐步决定是否选取当前物品。这种方法在处理不可分割物品或其他复杂约束时更为灵活，但通常会有更高的计算复杂度。