题解 | #称砝码#

动态规划真的有意思，这题可以转化为0/1背包问题。

有些麻烦的是，n个砝码每个都有不同的数量，所以不能只考虑取哪些砝码，而应该把所有砝码都视为独立个体，这个个体只有重量属性，因为只有一个属性，直接用weight数组表示，总数为所有的xi 加总。

因为只需要获取不同的重量情况，我们直接去重算set个数加上0的情况即可。

import java.util.*;

// 注意类名必须为 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 n = in.nextInt();
            int[] ms=new int[n];
            int[] xs=new int[n];
            
            for(int i=0;i<n;i++){
                ms[i]= in.nextInt();
            }
            for(int i=0;i<n;i++){
                xs[i] = in.nextInt();
            }

            
            int total=0;
            for(int i =0;i<xs.length;i++){
                total+=xs[i];
            }

            int[] weight=new int[total+1];

            int k=1;
            for(int i =0;i<n;i++){
                for(int j=1;j<=xs[i];j++){
                    weight[k]=ms[i];
                    k++;
                }
            }

            System.out.println(compute(weight));
        }
    }
    public static int compute(int[] weight){

        int counter=0;
        int max_weight=0;
        for(int i=1;i<=weight.length-1;i++){
            // System.out.println(weight[i]);
            max_weight+=weight[i];
        }

        int[] dp=new int[max_weight+1];
        Set<Integer> set=new HashSet<>();

        for(int i=1;i<=weight.length-1;i++){
            for(int j=max_weight;j>=0;j--){
                //动态规划
                if(j>=weight[i]){
                    dp[j]=Math.max(dp[j-weight[i]]+weight[i],dp[j]);
                    set.add(dp[j]);
                }
            }

        }

        return set.size()+1;
    }
}