dfs记住:找重复,找变化,找边界 来写dfs的函数。
预定义一个count数组,来存放0-100000的所有数据。每得到一个大于0的重量sum,就令count[sum] = 1。
最后打印count数组中为1的数,即可。
但是结果会超时,只能拿一半的分数。
private static void dfs(int x,int[] w,int sum,int[] count) {//下一个使用砝码的下标,砝码数组,当前用到砝码的总重量 if (x == w.length) { if (sum > 0) { count[sum] = 1; } return; } dfs(x+1,w,sum+w[x],count);//加上第x个砝码 dfs(x+1,w,sum,count);//不加第x个砝码 dfs(x+1,w,sum-w[x],count);//减去第x个砝码 }
import java.util.*; //背包 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = 100; int n = scanner.nextInt();//砝码总数 int[] w = new int[N+1]; //砝码大小 int M = 200000; int B = M/2; int s = 0;//砝码总重量 for (int i = 1; i <= n; i++) {//N个砝码的大小 w[i] = scanner.nextInt(); s += w[i]; } boolean[][] dp = new boolean[N+1][M+1]; dp[0][B] = true; //DP for (int i =1; i <= n; i++) { for (int j = -s; j <= s; j++) { dp[i][j+B] = dp[i-1][j+B]; if (j-w[i] >= -s) { dp[i][j + B] |= dp[i-1][j - w[i] + B]; } if (j+w[i] <= s) { dp[i][j + B] |= dp[i-1][j + w[i] + B]; } } } int count = 0; for (int j =1 ; j <=s; j++) { if (dp[n][j+B]) { count++; } } System.out.println(count); } }
import java.util.*; //dfs暴力 public class Main{ static int N = 100;//最大砝码数 static int M = 100000;//最大重量 static int[] count = new int[M+1]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt();//取的砝码数 int[] w = new int[n]; for (int i = 0; i < n; i++) { w[i] = scanner.nextInt();//砝码的大小 } //DFS dfs(0,w,0); //遍历count数组 int s = 0; for (int i = 0; i < count.length; i++) { if (count[i] == 1) { s++; } } //打印结果 System.out.println(s); } private static void dfs(int x,int[] w,int sum) {//下一个使用砝码的下标,砝码数组,当前用到砝码的总重量 // TODO Auto-generated method stub if (x == w.length) { if (sum > 0) { count[sum] = 1; } return; } dfs(x+1,w,sum+w[x]);//加上第x个砝码 dfs(x+1,w,sum);//不加第x个砝码 dfs(x+1,w,sum-w[x]);//减去第x个砝码 } }