跳至内容

拾光小记

货物装满最多箱子问题

/posts/%E8%B4%A7%E7%89%A9%E8%A3%85%E6%BB%A1%E6%9C%80%E5%A4%9A%E7%AE%B1%E5%AD%90%E9%97%AE%E9%A2%98/ map[avatar:https://avatars.githubusercontent.com/u/123456789?v=4 email:iworkvip@gmail.com location:China name:melonkid]

问题

有一批货，体积大小随机，有一批箱子，体积固定为3，不考虑货物的体积，求给定货物最多能装满几个箱子。

说明：体积为6的货物可以用2个箱子装完，体积为7的箱子不能被箱子装下

__

思路

当货物的体积为3的整数倍时，货物可以刚好装满箱子 当货物总体积除以3余1时，说明至少存在一个体积除3余1的货物，剔除其中最小的一个即可。 当货物体积除以3余2时，说明可能存在偶数个除3与1的货物或奇数个除3余2的货物。剔除2个最小除3余1的货物 或者剔除最小的一个除3余2的货物即可。
伪代码：

// 按顺序保存最小的除3余1两个货物
int[] mode1 = int[2];

// 保存最小的除3余2的一个货物
int mode2;

// 货物总体积
int sumVolum;

if(sumVolum % 3 == 0) {
	return sumVolum / 3;
}

if(sumVolum % 1 == 0) {
    return (sumVolum - mode1[0])/3;
}

// 说明不存在除3余1或者不存在偶数个除3余1的货物。那么就应该剔除除3余2的货物
if(mode1[1] == 0 || mode1[1] == 0) {
    return (sumVolum - mode2)/3;
}


int tmpSum = mode1[1] + mode1[1];
if(tmpSum > mode2) {
    return (sumVolum - mode2)/3;
}

return (sumVolum - tmpSum)/3;

这里有个技巧，就是如何一次循环得到倒数1，2的两个最小的货物。思路是：
如果mode1[0] == 0，就先填充mode1[0]。
如果校验货物的体积比mode1[0]小，替换mode1[0]为校验货物，并将mode1[0]之间的值放置到mode1[1]
如果校验货物的提交比mode1[0]大，但是mode1[1]==0。将检验货物放置到mode1[1]。
如果校验货物的体积比mode1[0]大，但比mode1[1]小，那么将检验货物放置到mode1[1]。

代码实现

public int solution(int[] arr) {
        // 分别记录除3余1和除3余2的货物
        int[] mode1 = new int[2];
        int mode2 = 0;

        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 3 == 1) {
                // 一个余数为1的数都没有
                if (mode1[0] == 0) {
                    mode1[0] = arr[i];
                    sum += arr[i];
                    continue;
                }

                // 将最小的放到mode1[0] 将次小的放到mode1[1]
                if (mode1[0] > arr[i]) {
                    mode1[1] = mode1[0];
                    mode1[0] = arr[i];
                    sum += arr[i];
                    continue;
                }

                if (mode1[1] > arr[i]) {
                    mode1[1] = arr[i];
                    sum += arr[i];
                    continue;
                }

                if (mode1[1] == 0) {
                    mode1[1] = arr[i];
                    sum += arr[i];
                    continue;
                }

            }

            if (arr[i] % 3 == 2) {
                if (mode2 == 0) {
                    mode2 = arr[i];
                    sum += arr[i];
                    continue;
                }

                if (mode2 > arr[i]) {
                    mode2 = arr[i];
                }
            }

            sum += arr[i];
        }

        int mode = sum % 3;
        if(mode == 0) {
            return sum / 3;
        }

        if (mode == 1) {
            return (sum - mode1[0]) / 3;
        }

        if(mode1[0] == 0 || mode1[1] == 0) {
            return (sum - mode2) / 3;
        }

        int nums = mode1[0] + mode1[1];
        if (nums > mode2) {
            return (sum - mode2) / 3;
        }

        return (sum - nums) / 3;
    }

校验代码

int[] arr = {3, 6, 5, 1, 8};
int ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 6, MelonStatusCodeEnums.SYSTEM_ERROR);

arr = new int[]{3, 6, 5, 1, 5, 1, 8};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 9, MelonStatusCodeEnums.SYSTEM_ERROR);

arr = new int[]{5};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 0, MelonStatusCodeEnums.SYSTEM_ERROR);

arr = new int[]{5, 1};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 2, MelonStatusCodeEnums.SYSTEM_ERROR);

arr = new int[]{5, 1};
ret = maxBoxProblem.solution(arr);
AssertUtil.assertTrue(ret == 2, MelonStatusCodeEnums.SYSTEM_ERROR);

继续阅读