题解 | #称砝码，背包问题，动态规划#

import java.util.* ;
public class Main{
    public static void main(String...args) {
        Scanner sc = new Scanner(System.in) ;
        while(sc.hasNextLine()) {
            Integer n = Integer.parseInt(sc.nextLine()) ;
            int W[] = new int[n] ;
            int T[] = new int[n] ;
            for(int i = 0 ; i < n ; i ++) {
                W[i] = sc.nextInt();
            }
            sc.nextLine() ;
            for(int i = 0 ; i < n ; i ++) {
                T[i] = sc.nextInt();
            }
            sc.nextLine() ;
            int count = 0 ;//总个数
            int sum = 0 ;//总重量（背包的总沉重）
            for(int i = 0 ; i < n ; i ++) {
                sum += W[i]*T[i] ;
                count += T[i] ;
            }
            //把砝码平摊开表示，每个砝码当成互相独立的砝码
            int W2[] = new int[count] ;//1,1,2
            int t = 0 ;
            for(int i = 0 ; i < n ; i ++) {
                for(int j = 0 ; j < T[i] ; j ++) {
                    W2[t++] = W[i] ;
                }
            }
            System.out.println(haoManyDiff(W2,sum)) ;
        }
    }
    public static int haoManyDiff(int[] W , int all) {
        int len = W.length ; 
        boolean f[][] = new boolean[len+1][all+1] ;//f[i][j]表示前i个砝码，能否拼出重量j
        f[0][0] = true ;
        for(int i = 1 ; i <= all ; i ++) {//注意：从1开始，因为f[0][0]已经初始化了
            f[0][i] = false ;
        }
        for(int i = 1 ; i <= len ; i ++) {
            for(int j = 0 ; j <= all ; j ++) {
                //转移方程，第i-1个物品，可能放得下，可能放不下
                //f[i][j] = f[i-1][j]&nbs***bsp;f[i-1][j-W[i-1]]
                f[i][j] = f[i-1][j] ;
                if(j >= W[i-1]) {
                     f[i][j] = f[i][j] || f[i-1][j-W[i-1]] ;
                }
            }
        }
        int ret = 0 ;
        for(int i = 0 ; i <= all ; i ++) {
            if(f[len][i]) {
                ret ++ ;
            }
        }
        return ret ;
    }
}