全部评论
第一题01背包public static int ks(int[] day, int[] value, int day1) { int size = day.length; if (size == 0) { return 0; } int[][] dp = new int[size][day1 + 1]; for (int i = 0; i <= day1; i++) { dp[0][i] = day[0] <= i ? value[0] : 0; } for (int i = 1; i < size; i++) { for (int j = 0; j <= day1; j++) { dp[i][j] = dp[i - 1][j]; if (day[i] <= j) { dp[i][j] = Math.max(dp[i][j], value[i] + dp[i - 1][j - day[i]]); } } } return dp[size - 1][day1]; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int num=scan.nextInt(); for(int i=0;i<num;i++) { int num1=scan.nextInt(); int day=scan.nextInt(); int[] value=new int [num1]; int []day1=new int[num1]; for(int j=0;j<num1;j++) { value[j]=scan.nextInt(); day1[j]=scan.nextInt(); } System.out.println(ks(day1,value,day)); } } 第三题我是用的递归求解约束判断 因为会重复的 所有我先存了一下判断,代码比较low 不 喜勿喷 public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan=new Scanner(System.in); int num1=scan.nextInt(); int num2=scan.nextInt(); int [] price=new int[num2]; for(int i=0;i<num2;i++) { price[i]=scan.nextInt(); } int like=scan.nextInt(); int []likeall=new int[like]; for(int i=0;i<like;i++) { likeall[i]=scan.nextInt()-1; } int []count=new int[num2]; int []countall=new int[1]; countall[0]=0; int [] []flagg=new int[1000][num2]; int []nums={0}; dfs(num1,price,count,likeall,countall,flagg,nums); System.out.print(countall[0]); } public static void dfs(int num,int []price,int []count,int []like,int []countall,int[][]flagg,int[] nums) { for(int i=0;i<price.length;i++) { num=num-price[i]; count[i]++; if(num<0){ count[i]--; return; } if(num==0) { int flag=1; for(int j=1;j<like.length;j++) { if(count[like[j]]-count[like[j-1]]>=0) { flag=0; } } if(flag==1) { for(int q=0;q<flagg.length;q++) { int flags=0; for(int y=0;y<count.length;y++) { if(flagg[q][y]!=count[y]) { flags=1; break; } } if(flags==0) { count[i]--; return; } } for(int x = 0;x<count.length;x++) { flagg[nums[0]][x]=count[x]; } nums[0]++; countall[0]++; } count[i]--; return ; } if(num>0) { dfs(num,price,count,like,countall,flagg,nums); count[i]--; num=num+price[i]; } } return; }
相关推荐