U - Inviting Friends HDU - 3244(二分答案 + 完全背包)
U - Inviting Friends HDU - 3244
You want to hold a birthday party, inviting as many friends as
possible, but you have to prepare enough food for them. For each
person, you need n kinds of ingredient to make good food. You can use
the ingredients in your kitchen, or buy some new ingredient packages.
There are exactly two kinds of packages for each kind of ingredient:
small and large.We use 6 integers to describe each ingredient: x, y, s1, p1, s2, p2,
where x is the amount (of this ingredient) needed for one person, y is
the amount currently available in the kitchen, s1 and p1 are the size
(the amount of this ingredient in each package) and price of small
packages, s2 and p2 are the size and price of large packages.Given the amount of money you can spend, your task is to find the
largest number of person who can serve. Note that you cannot buy only
part of a package. Input There are at most 10 test cases. Each case
begins with two integers n and m (1<=n<=100, 1<=m<=100000), the number
of kinds of ingredient, and the amount of money you have. Each of the
following n lines contains 6 positive integers x, y, s1, p1, s2, p2 to
describe one kind of ingredient (10<=x<=100, 1<=y<=100, 1<=s1<=100,
10<=p1<=100, s1<s2<=100, p1<p2<=100). The input ends with n = m = 0.
Output For each test case, print the maximal number of people you can
serve. Sample Input
2 100
10 8 10 10 13 11
12 20 6 10 17 24
3 65
10 5 7 10 13 14
10 5 8 11 14 15
10 5 9 12 15 16
0 0
Sample Output
5
2
思路
- 这一题挺不错的,把 二分的知识 与 背包问题的知识放在一起来考察我们,这一题我们要二分的是 招待的 friend 的数量, 而我们一但二分答案假设出一个 朋友数量,我们就需要判断 用厨房里剩余的菜 + 手里的钱
最新文章
- html5上传图片(一)一跨域上传
- not in 和 not EXISTS 的区别
- AWS EC2首次使用VPS
- OS初识
- c# windows编程控件学习-1
- Daily Scrum – 1/19
- tesseract-orc 合并识别结果
- 导出excel小结(C#,.NET,Wpf)
- CentOS下shell显示-bash-4.1#不显示用户名路径的解决方法
- linux内核分析系列--百度
- django获取某一个字段的列表,values/values_list/flat
- 自写jquery网页回到顶部效果,渐隐图标,引用js文件就可以
- elk 5.x的部署
- UEP-弹窗
- SQL语句报错(一)
- 状态模式-State Pattern(Java实现)
- Oracle sql function LISTAGG
- SpringBoot整合ssm
- 我的C语言编程风格
- ping + traceroute + tracert + tcpdump等命令的原理
热门文章