题目描述:
有一堆商品,每个商品有一个重量和价值。你有一个背包,背包的最大承重为 C,你需要从商品中选择一部分商品放入背包,使得总价值最大化。商品可以被分割,即你可以选择一部分商品放入背包。
输入格式:
输出格式:
输出一个浮点值,表示背包中放入商品后能得到的最大价值。结果保留 2 位小数。
示例:
输入:
4 12
2 3
4 4
3 4
5 8
输出:
17.00
说明:
在解决一些优化问题时,我们通常需要找出最优解(例如:最大化、最小化)。而贪心算法(Greedy Algorithm)是一种常用的求解方法,它的基本思想是:在每一步选择中都采取当前最优的选择,以期得到全局的最优解。
具体来说,贪心算法有以下特点:
局部最优选择:在每个阶段或步骤中,选择当前最优的解决方案,通常是选择那个“最好”的选项。
不考虑全局情况:在每一步的决策中,贪心算法并不考虑未来的步骤,也不关心当前选择对后续的影响。它只专注于当前问题的最优解,而不是全局最优解。
贪心策略的正确性:有时候,贪心算法能给出最优解,但并不是所有的优化问题都能通过贪心算法找到全局最优解。在能通过贪心算法找到最优解的情况下,这种算法非常高效。
假设在某个最优解中,某些选择的顺序与贪心算法的选择顺序不一致。通过交换这些选择,证明交换后的解并不比原解差,或者至少能得到相同的最优解,从而证明贪心算法能得到全局最优解。
在贪心算法中,归纳法常用于证明每一步选择的局部最优性能够导致全局最优解。在归纳步骤中,我们假设贪心算法对于较小规模问题的正确性,然后证明它对较大规模问题也能成立。
通常来说,使用贪心算法的步骤如下:
选择标准:确定每一步选择的标准,即选择当前最优的选项。
选择过程:通过选择当前的最优解,逐步逼近问题的全局最优解。
可行性检查:在选择过程中,要随时检查当前选择是否符合问题的约束条件。
问题的最终解:在所有步骤完成后,得出最终的解。
题目简述:
本题是一个典型的“分数背包问题”(Fractional Knapsack Problem)。给定一组商品,每个商品有一个重量和价值,背包有一个最大承重限制。你需要从商品中选择一部分商品放入背包,目标是最大化背包中的总价值。值得注意的是,商品是可以分割的,因此你可以选择将商品的一部分放入背包。
贪心算法的思路:
在这个问题中,贪心算法的策略是:每次选择单位重量价值最高的商品放入背包。这样能够保证在每一步做出的选择都是最优的,从而实现全局最优解。
具体而言,贪心的选择标准是:对于每个商品,计算其单位重量的价值,即“价值/重量”。然后,按照单位重量价值从大到小的顺序进行排序,依次将商品放入背包,直到背包的承重限制达到最大值。
贪心正确性证明(交换法):
假设在某一步先选择了性价比较低的物品,之后根据剩余容量我们再选择性价比高的物品,最终获得的价值总和不会高于贪心选择的解。因此,贪心算法是最优的。
解题思路:
输入处理:首先读取商品的数量和背包的最大承重,并读取每个商品的重量和价值。
计算单位重量价值:对于每个商品,计算单位重量的价值,记为“价值/重量”。然后,将所有商品按单位重量价值进行排序,单位重量价值高的商品优先放入背包。
放入背包:从排序后的商品中依次选择,如果背包能够装下当前商品,则直接放入;如果不能装下当前商品,就将剩余空间装入部分商品。
输出结果:输出最终放入背包中的总价值,保留两位小数。
代码实现:
def fractional_knapsack(n, C, items):
# 计算每个商品的单位重量价值
items_with_ratio = []
for weight, value in items:
ratio = value / weight # 计算单位重量的价值
items_with_ratio.append((weight, value, ratio))
# 按照单位重量价值从大到小排序
items_with_ratio.sort(key=lambda x: x[2], reverse=True)
total_value = 0.0 # 总价值初始化为0
remaining_capacity = C # 剩余背包容量
for weight, value, ratio in items_with_ratio:
if remaining_capacity == 0: # 背包已满
break
if weight <= remaining_capacity: # 商品能完全放入背包
total_value += value
remaining_capacity -= weight
else: # 只能放入部分商品
total_value += value * (remaining_capacity / weight)
remaining_capacity = 0 # 背包满了
# 输出最终的总价值,保留两位小数
return round(total_value, 2)
# 输入部分
n, C = map(int, input().split()) # 读取商品数量n和背包最大承重C
items = []
for _ in range(n):
w, v = map(int, input().split()) # 读取每个商品的重量w和价值v
items.append((w, v))
# 计算并输出结果
result = fractional_knapsack(n, C, items)
print(f"{result:.2f}")