动态规划：分割等和子集（01背包问题）

//本题目可以转换为:容量为num/2的背包,这n个物品的体积和价值都相等,求dp[sum/2]是否等于sum/2
class Solution {
   public boolean canPartition(int[] nums) {
        int target=0;
        for (int num : nums) {
            target+=num;
        }
        if (target%2!=0) return false;
        target/=2;
        int []dp=new int[target+1];
        Arrays.fill(dp,0);
        for (int i = 0; i <nums.length ; i++) {
            for (int j = target; j >=nums[i] ; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if (dp[target]==target) return true;
        else return false;
    }
}
//当dp[target]=target,说明在sum/2的容量下,里面的数字之和刚好也为sum/2
//01背包不仅能解决最大价值问题,还可以解决能否装满背包的问题