Processing math: 100%
祝同学们学习进步，编程快乐！
Problem 2702 --15_B : Fractional Knapsack Problem

2702: 15_B : Fractional Knapsack Problem

上一题 正确率: 0.00\% 下一题
"
Time Limit 1 秒/Second(s) Memory Limit 512 兆字节/Megabyte(s)
提交总数 0 正确数量 0
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

Description

Fractional Knapsack Problem

You have NN items that you want to put them into a knapsack of capacity WW. Item ii (1≤i≤N1≤i≤N) has weight wiwi and value vivi for the weight.

When you put some items into the knapsack, the following conditions must be satisfied:

  • The total value of the items is as large as possible.
  • The total weight of the selected items is at most WW.
  • You can break some items if you want. If you put w′w′(0≤w′≤wi0≤w′≤wi) of item ii, its value becomes vi×w′wi.vi×w′wi.

Find the maximum total value of items in the knapsack.

Input

Input 

NN WW v1v1 w1w1 v2v2 w2w2 : vNvN wNwN

The first line consists of the integers NN and WW. In the following NN lines, the value and weight of the ii-th item are given.

Output

Output

Print the maximum total value of the items in a line. The output must not contain an error greater than 10−610−6.

Sample Input复制

3 50
60 10
100 20
120 30

Sample Output复制

240

提示

Constraints

  • 1≤N≤1051≤N≤105
  • 1≤W≤1091≤W≤109
  • 1≤vi≤109(1≤i≤N)1≤vi≤109(1≤i≤N)
  • 1≤wi≤109(1≤i≤N)1≤wi≤109(1≤i≤N)


推荐代码 查看2702 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[ ms]
内存最少[ KB]
第一AC
第一挑战

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛
AOJ
祝同学们学习进步，编程快乐！