import java.util.*;
public class Main {

    public static int min=Integer.MAX_VALUE;//定义一个全局的min
    public static void main(String[] args) {

        int[] arr = {30,60,5,15,30}; //期待输出是20
        int sum=0;
        for(int num:arr)
            sum+=num;

        selectHelper(0,0,0,sum,arr);
        System.out.println(min);

    }
    //用户1当前的总数，用户2当前的总数，第i个物品,总的sum和，arr数组
    //决策树！决策树！决策树！
    public static void selectHelper(int user1,int user2,int i,int sum,int[]arr)
    {
        //边界条件
        if(user1==user2)
            min=Math.min(min,sum-user1-user2);
        if(i>=arr.length)
            return;
        //做决策
        //把第i个物品给用户1
        selectHelper(user1+arr[i],user2,i+1,sum,arr);
        //把第i个物品给用户2
        selectHelper(user1,user2+arr[i],i+1,sum,arr);
        //第i个物品谁都不给
        selectHelper(user1,user2,i+1,sum,arr);
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {

        int[] a = {30,60,5,15,30}; //期待输出是20
        //int[] a = {30,20,5,20,30};
        System.out.println(diff(a));

    }

    public static int diff(int[]a)
    {
        int len=a.length;
        int sum=0;
        for(int i=0;i<len;i++)
            sum+=a[i];

        int[][]dp=new int[len+1][sum/2+1];

        //dp[i][j]定义：前i个物品，能够凑出最接近j的数值

        for(int i=0;i<=len;i++)
            for(int j=0;j<=sum/2;j++)
                dp[i][j]=0;


        for(int i=1;i<=len;i++)
            for(int j=1;j<=sum/2;j++)
                if(j>=a[i-1])
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-a[i-1]]+a[i-1]);
                else
                    dp[i][j]=dp[i-1][j];

        System.out.println(dp[len][sum/2]);
        //我知道这道题错在哪了，测试用例的数值凑巧对了，但是dp转移其实是错误的。因为测试用例的dp[len][sum/2]输出是65
        //但实际上需要输出的是60。
        //这样的dp转移并不能保证，两个数拿的是一样的。

        return sum-2*dp[len][sum/2];
    }
}