题解 | #[NOIP2001]装箱问题#

import java.util.Scanner; 

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int target=in.nextInt();
        int n=in.nextInt();
        int[] volumes=new int[n];
        for(int i=0;i<n;i++){
            volumes[i]=in.nextInt();
        }
        boolean[]  dp=new boolean[target+1];  //dp[j]中j代表物品加起来的的体积，dp代表是否达到这个体积
        dp[0]=true;
        for(int volume:volumes){
            for(int j=target;j>=volume;j--){
                dp[j]=dp[j]||dp[j-volume];
            }
        }
        for(int j=target;j>=0;j--){
            if(dp[j]){
                int lefted_volume=target-j;
                System.out.println(lefted_volume);
                return;
            }
        }

    }
}

①定义逻辑数组：boolean[] dp=new boolean[target+1]; //dp[j]中j代表物品加起来的的体积，dp代表是否达到这个体积

②创建初始dp值： dp[0]=true

③对每一个物品体积进行遍历，跟新dp数组。并且用上逻辑运算符号或|| ： for(int j=target;j>=volume;j--) dp[j]=dp[j]||dp[j-volume];

④找到离target值最近的j,就是自己想要的数字