黑马程序员技术交流社区

标题: 关于小明女朋友买买买-最大种类问题-贪心算法 [打印本页]

---

作者: 小江哥    时间: 2019-1-22 13:28
标题: 关于小明女朋友买买买-最大种类问题-贪心算法


近期遇到的面试题：
小明的女朋友最喜欢在网上买买买了，可是钱包里钞票有限，不能想买啥就买啥。面对琳琅满目的物品，她想买尽可能多的种类，每种只买一件，同时总价格还不能超过预算上限。于是她请小明写程序帮她找出应该买哪些物品，并算出这些物品的总价格。

输入规范：
每个输入包含两行。第一行是预算上限。第二行是用空格分隔的一组数字，代表每种物品的价格。所有数字都为正整数并且不会超过10000。

输出规范：
对每个输入，输出应买物品的总价格。

输入示例1:
100
50 50
输出示例1:
100

输入示例2:
188
50 42 9 15 105 63 14 30
输出示例2:
160

解题思路：首先商品的种类不是固定的(可以输入若干商品价格)，我采用集合ArrayList来存放商品价格，然后进行从小到大排序，遍历该集合，
如果当前拥有的钱 total 大于该物品价格price，则说明可以购买，
当前的钱减去该商品    价格total = total-price，
总价增加 sum+= price,若当前拥有的钱，小于price，则说明无法购买，跳出循环，打印总价sum。
暂时不考虑复杂度

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2