#yyds干货盘点# 名企真题专题：最少数量货物装箱问题

1.简述：

描述

有重量分别为 3，5，7 公斤的三种货物，和一个载重量为 X 公斤的箱子（不考虑体积等其它因素，只计算重量）

需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）

数据范围： 

输入描述：

输入箱子载重量(一个整数)。

输出描述：

如果无法装满，输出 -1。如果可以装满，输出使用货物的总个数。

示例1

输入：

4

输出：

-1

说明：

无法装满

示例2

输入：

8

输出：

2

说明：

使用1个5公斤，1个3公斤货物

2.代码实现：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][] dp=new int[n+1][4];
        int[] nums=new int[]{3,5,7};
        for(int i=0;i<=n;i++)
            dp[i][0]=Integer.MAX_VALUE;
        //dp[n][3]=;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=3;j++){
                if(i-nums[j-1]<0)
                    dp[i][j]=dp[i][j-1];
                else{
                    if(dp[i-nums[j-1]][j]==Integer.MAX_VALUE)
                        dp[i-nums[j-1]][j]=Integer.MAX_VALUE-1;
                    dp[i][j]=Math.min(dp[i][j-1],dp[i-nums[j-1]][j]+1);
                }

            }

        }
        System.out.println(dp[n][3]==Integer.MAX_VALUE?-1:dp[n][3]);
    }
}