题解 | #兑换零钱#

完全背包 至少装满时，最大价值/最少货币数

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int aim = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < n; i++) {//物品
            for(int j = arr[i]; j <= aim; j++) {
                if(dp[j - arr[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
                }
                
            }
        }
        System.out.println((dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim]));
    }
}