【贪心1】选商品
贪心算法介绍:
在解决一些优化问题时,我们通常需要找出最优解(例如:最大化、最小化)。而贪心算法(Greedy Algorithm)是一种常用的求解方法,它的基本思想是:在每一步选择中都采取当前最优的选择,以期得到全局的最优解。
具体来说,贪心算法有以下特点:
- 局部最优选择:在每个阶段或步骤中,选择当前最优的解决方案,通常是选择那个“最好”的选项。
题目描述:
有一堆商品,每个商品有一个重量和价值。你有一个背包,背包的最大承重为 C,你需要从商品中选择一部分商品放入背包,使得总价值最大化。商品可以被分割,即你可以选择一部分商品放入背包。
输入格式:
- 第一行包含两个整数 n 和 C,分别表示商品的数量和背包的最大承重。(2<=n<=105),(1<=C<=105)
- 接下来的n行,每行包含 2 个整数,格式为 (w1,v1),(w2,v2),...,(wn,vn),其中 wi 表示商品的重量,vi 表示商品的价值。(1<=wi,vi<=100)
输出格式:
输出一个浮点值,表示背包中放入商品后能得到的最大价值。结果保留 2 位小数。
示例:
输入:
4 12
2 3
4 4
3 4
5 8
输出:
17.00
说明:
- 选择第一个商品(2,3),全部放入背包中。价值为3。
- 选择第二个商品(4,4),取出重量2,放入背包中。价值为2。
- 选择第三个商品(3,4),全部放入背包中。价值为4。
- 选择第四个商品(5,8),全部放入背包中。价值为8。
- 总价值为 17.00。