题解 | #分割等和子集#
分割等和子集
https://www.nowcoder.com/practice/65ade309fa4d4067a9add749721bfdc0
利用01背包问题的变形：
1.首先求和后确定是否奇数，是则返回false；
2.我们要求这道题可以变形成求一个背包能否被装满，而背包容量为bag=sum/2；
3.如果背包能被装满则剩下的值之和也是sum/2，所以要求背包能否被装满利用01背包问题，建dp[bag+1]，
我们可以想象，变形成求最少或者最多需要多少个物品让背包装满。这里是最多多少物品能让背包装满。所以dp初值为Integer.MIN_VALUE;
我们利用背包问题模型，解出来的dp[bag]如果等于Integer.MIN_VALUE;说明没有办法让背包装满。返回false，反之返回true。
import java.util.*;
public class Main{
public static boolean process(int[] arr,int n){
int sum=0;
for(int a:arr)
sum+=a;
if((sum&1)!=0)
return false;
int bag=sum/2;
int[]dp=new int[bag+1];
Arrays.fill(dp,Integer.MIN_VALUE);
dp[0]=0;
for(int i=1;i<=bag;i++){
for(int j=0;j<arr.length;j++){
if(arr[j]<=i&&dp[i-arr[j]]!=Integer.MIN_VALUE){
dp[i]=Math.max(dp[i],dp[i-arr[j]]+1);
}
}
}
return dp[bag]==Integer.MIN_VALUE?false:true;
}
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[]arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
System.out.print(process(arr,n));
}
}
投递科锐国际等公司10个岗位