第一题,0-1背包问题:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int money = scanner.nextInt(); int n = scanner.nextInt(); int[] price = new int[n]; int[] value = new int[n]; for (int i = 0; i < n; i++) { price[i] = scanner.nextInt(); value[i] = scanner.nextInt(); } System.out.println(maxValue(money, n, price, value)); } private static int maxValue(int money, int n, int[] price, int[] value) { int[][] dp = new int[n + 1][money + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= money; j++) { if (price[i - 1] > j) dp[i][j] = dp[i - 1][j]; else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - price[i - 1]] + value[i - 1]); } } return dp[n][money]; } }本地测试用例全部正确,提交系统通过0%,找了 很久没发现问题出现在哪里,服了🙂!!!
第二题:全排列找能被7整除的数
package com; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static List<String> res = new ArrayList<>(); static StringBuilder sb = new StringBuilder(); static boolean[] used; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); String[] str = s.substring(1, s.length() - 1).split(","); int[] a = new int[str.length]; used = new boolean[a.length]; for (int i = 0; i < a.length; i++) a[i] = Integer.parseInt(str[i]); System.out.print(reletive_7(a)); } public static int reletive_7(int[] digit) { pailie(digit, sb, used); int count = 0; int[] a = new int[res.size()]; for (int i = 0; i < res.size(); i++) { a[i] = Integer.parseInt(res.get(i)); if (a[i] % 7 == 0) count++; } return count; } private static void pailie(int[] num, StringBuilder sb, boolean[] used) { if (sb.length() == num.length) { res.add(sb.toString()); return; } for (int i = 0; i < num.length; i++) { if (used[i]) continue; used[i] = true; sb.append(String.valueOf(num[i])); pailie(num, sb, used); used[i] = false; sb.deleteCharAt(sb.length() - 1); } } }本地测试很多用力全部正确,系统通过25%,提示数据越界;没发现哪里越界了🙂
两道简单的编程AC了0.25,真是服了!!
全部评论
(7) 回帖