题解 | #最少数量货物装箱问题#

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            System.out.println(calc(a));
        }
    }
	/**
	 * 这个题目写了其他的解法，但是经过思考后觉得题目中的3种货物的重量如果发生变化后，在一些特殊组合的时候
	 * 之前的方法就会有漏洞，觉得下面的解题思路才能覆盖货物变化后的结果
	 * case1：当货物的重量分别为：8 6 2的时候，x总重量为20，之前的解题思路（calcOld方法），
	 * 可能结果为：8，8，2，2；实际结果为：8，6，6
	 * case2：当货物的重量分别为：9 4 3的时候，x总重量为12，如果按照先从重的货物组合的话，
	 * 可能会得到结果为：4，4，4；实际结果为：9，3
	 * 所以为了覆盖所有可能，需要将所有组合计算出来，最后取出最少的一组，第一种组合，最重的一种；第二种组
	 * 合为最终的两种货物；第三种组合为从重到轻依次递减组合，也就是最早的解题思路（calcOld方法）
	 * 最终的算法算是对题目的升级版，也就是说货物重量和箱子的载重都可变
	 */
    private static int calcOld(int a) {
        int h1 = 3;
        int h2 = 5;
        int h3 = 7;
        int max7 = a / h3;
        int max5 = 0;
        int max3 = 0;
        int i7 = max7;
        int i5 = 0;
        int i3 = 0;
        for (; i7 >= 0; i7--) {
            max5 = (a - i7 * h3) / h2;
            int a2 = (a - i7 * h3);
            i5 = max5;
            for (; i5 >= 0; i5--) {
                if ((a2 - i5 * h2) % h1 == 0) {
                    max3 = (a2 - i5 * h2) / h1;
                    return (i7 + i5 + max3);
                }
            }
        }
 
        return -1;
    }
    private static int calc(int a) {
        int h1 = 3;
        int h2 = 5;
        int h3 = 7;
        
        // 最重的货物直接装满
        if(a % h3 == 0){
            return a / h3;
        }
        
        // 尝试用最重的两种货物装满
        int result1 = -1;
        int n1 = a / h3;
        while(n1 >= 0){
            int unUse1 = a - n1 * h3;
            if(unUse1 % h2 == 0){
                // 满足条件，退出循环
                result1 = n1 + unUse1 / h2;
                break;
            }
            // 去掉一个最重的货物再尝试
            n1--;
        }

        // 最后尝试三种货物组合
        int result2 = -1;
        n1 = a / h3;
        // 是否结束循环
        boolean flag = false;
        while(n1 >= 0){
            int unUse1 = a - n1 * h3;
            int n2 = unUse1 / h2;
            while(n2 >= 0){
                int unUse2 = unUse1 - n2 * h2;
                if(unUse2 % h1 == 0){
                    result2 = n1 + n2 + unUse2 / h1;
                    flag = true;
                    break;
                }
                n2--;
            }
            if(flag){
                break;
            }
            // 去掉一个最重的货物再尝试
            n1--;
        }

        if(result1 == -1){
            // 当最重的两种货物组合无法装满时，返回三种货物组合结果
            return result2;
        }
        if(result2 == -1){
            // 当三种货物组合无法装满时，返回最重的两种货物组合结果
            return result1;
        }

        if(result1 == -1 && result2 == -1){
            // 所有组合都无法装满
            return -1;
        }
        // 当最终的两种货物组合和三种货物组合都能装满时，返回数量最少的那个组合结果
        return result1 > result2 ? result2 : result1;
    }
}