【LeetCode】装满石头的背包的最大数量 Java 题解

作者：Albert

2022 年 7 月 06 日
本文字数：1173 字
阅读完需：约 4 分钟

题目描述

现有编号从 0 到 n - 1 的 n 个背包。给你两个下标从 0 开始的整数数组 capacity 和 rocks 。第 i 个背包最大可以装 capacity[i] 块石头，当前已经装了 rocks[i] 块石头。另给你一个整数 additionalRocks ，表示你可以放置的额外石头数量，石头可以往任意背包中放置。

请你将额外的石头放入一些背包中，并返回放置后装满石头的背包的最大数量。

示例 1：
输入：capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2输出：3解释：1 块石头放入背包 0 ，1 块石头放入背包 1 。每个背包中的石头总数是 [2,3,4,4] 。背包 0 、背包 1 和 背包 2 都装满石头。总计 3 个背包装满石头，所以返回 3 。可以证明不存在超过 3 个背包装满石头的情况。注意，可能存在其他放置石头的方案同样能够得到 3 这个结果。
示例 2：
输入：capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100输出：3解释：8 块石头放入背包 0 ，2 块石头放入背包 2 。每个背包中的石头总数是 [10,2,2] 。背包 0 、背包 1 和背包 2 都装满石头。总计 3 个背包装满石头，所以返回 3 。可以证明不存在超过 3 个背包装满石头的情况。注意，不必用完所有的额外石头。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/maximum-bags-with-full-capacity-of-rocks著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是背包问题，题目以数组的形式展现。题目比较长，给出了 capacity 和 rocks 两个数组，capacity 代表存储容量， rocks 代表当前已经有的数量，利用这两个数组，capacity[i] 减去 rocks[i], 可以求出 i 还可以放多少石头。
additionalRocks 代表还可以放的石头的总数，我们把 additionalRocks 放完，就可以求出背包的最大数量。
在求出背包的最大数量的时候，我们可以使用贪心的思想，也就是先放满差值数量小的背包。使用贪心，需要先对差值数组排序，然后先放满小的，在放满大的。具体实现代码如下，请参考。

通过代码

class Solution {    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {        int n = capacity.length;        int[] temp = new int[n];        int i = 0;        for (i = 0; i < n; i++) {            temp[i] = capacity[i] - rocks[i];        }
        int ans = 0;        Arrays.sort(temp);        for (i = 0; i < n; i++) {            if (additionalRocks >= temp[i]) {                additionalRocks -= temp[i];                temp[i] = 0;                ans++;            } else {                break;            }        }        return ans;    }}