题解 | 兑换零钱

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();//n and Volume
        // 这里我把价值和重量的字母正常写了，而非像题目那样有点反直觉        
        int []w = new int [n]; //weight
        for(int i=0;i<n;++i){
            w[i] = in.nextInt();            
        }
        // 求解问题二
        int []dp2 = new int [V + 1];        
        Arrays.fill(dp2, Integer.MAX_VALUE - 1);
        dp2[0] = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = w[i]; j <= V; ++j) {
                dp2[j] = Math.min(dp2[j - w[i]] + 1, dp2[j]);//价值默认为1，同时代表物品数
            }
        }
        if (dp2[V] > 1e4)//超出数据范围的物品数
            dp2[V] = -1;//无解
        System.out.println(dp2[V]);
        
    }
}