uva-562

题意

给出很多数字，分成差值最小的两部分，求最小差值。

思路

01背包原型为：在重量不超过sum/2的情况下，放入最多重量。

import java.util.*; public class Main{ static final int maxn=50002; public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int corn[]=new int[105]; int i,j; while(n-->0){ int[]dp=new int[maxn]; int m=sc.nextInt(); int sum=0; for(i=0;i<m;i++){ corn[i]=sc.nextInt(); sum+=corn[i]; } for(i=0;i<m;i++) for(j=sum;j>=corn[i];j--) if(Math.abs(sum-2*dp[j])>Math.abs(sum-2*(dp[j-corn[i]]+corn[i]))) dp[j]=dp[j-corn[i]]+corn[i]; int min=(int) Math.pow(10,9); for(i=0;i<=sum;i++) if(min>Math.abs(sum-2*dp[i])) min=Math.abs(sum-2*dp[i]); System.out.println(min); } } } }

二维数组

import java.util.*; public class Main{ static final int maxn=50002; public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int coin[]=new int[105]; int i,j; while(n-->0){ int[][]dp=new int[105][maxn]; int m=sc.nextInt(); int ssum=0; for(i=1;i<=m;i++){ coin[i]=sc.nextInt(); ssum+=coin[i]; } int sum=ssum/2; for(i=1;i<=m;i++) for(j=0;j<=sum;j++){ dp[i][j]=dp[i-1][j]; if(j>=coin[i]) dp[i][j]=dp[i][j]>(dp[i-1][j-coin[i]]+coin[i])?dp[i][j]:(dp[i-1][j-coin[i]]+coin[i]); } System.out.println(ssum-2*dp[m][sum]); } } } }

一维数组

import java.util.*; public class Main { static final int maxn = 50002; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n=sc.nextInt(); int[]coin=new int[105]; int i,j; while(n-->0){ int[]dp=new int[maxn]; int m=sc.nextInt(); int sum=0; for(i=0;i<m;i++){ coin[i]=sc.nextInt(); sum+=coin[i]; } int ssum=sum/2; for(i=0;i<m;i++) for(j=ssum;j>=coin[i];j--){ if(dp[j]<dp[j-coin[i]]+coin[i]) dp[j]=dp[j-coin[i]]+coin[i]; } System.out.println(sum-2*dp[ssum]); } } } }