関小君刷题记

题目大意：

最多可以买到的苹果数量

有一些苹果，arr[i]代表第i个苹果的重量，你还有一个篮子，最多可以装5000单位重量的苹果。

请返回最多可以装进篮子多少个苹果。

示例1:

Input: arr = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

示例2:

Input: arr = [900,950,800,1000,700,800]
Output: 5
Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

提示：

• 1 <= arr.length <= 10^3
• 1 <= arr[i] <= 10^3

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1196

解题思路分析：

本题可以利用贪心算法，先将数组排序，然后由轻到重向篮子里放，直到总重量超过5000为止，所装下的苹果个数即是答案。

证明该贪心算法很容易，因为数组已经排序，没装进篮子的苹果重量一定大于等于当前篮子中任意一个，因此用剩下的去替换篮子中的苹果会得不偿失。

实现代码：

public int maxNumberOfApples(int[] arr) {
    Arrays.sort(arr);
    int basket=5000;
    for(int i=0;i<arr.length;i++){
        basket-=arr[i];
        if(basket<0) return i;
    }
    return arr.length;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.51% of Java online submissions for How Many Apples Can You Put into the Basket.

Memory Usage: 38.7 MB, less than 100.00% of Java online submissions for How Many Apples Can You Put into the Basket.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1196-how-many-apples-can-you-put-into-the-basket-解题思路分析/