奇安信8.1笔试编程题（Java岗）

第一题

01背包问题，输入总预算，物资种类、价格和使用价值，求最大使用价值。
通过率100%。

import java.util.Scanner;

public class Money {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int allMoney = sc.nextInt();
        int n = sc.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        int[][] dp = new int[n + 1][allMoney + 1];

        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < allMoney + 1; j++) {
                if (j >= w[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j - w[i - 1]] + v[i - 1], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        System.out.print(dp[n][allMoney]);
    }
}

第二题

亲7数，即能被7整除的数。给出n个数的数字数组，通过排列组合成n位数，重复也要计算，找出其中的亲7数。
通过率100%。

import java.util.ArrayList;

public class ReletiveSeven {
    public static void main(String [] args) {
        ReletiveSeven rs = new ReletiveSeven();
        System.out.println(rs.reletive_7(new int[]{1,1,2}));
    }

    private ArrayList<Integer> list = new ArrayList<>();
    private boolean[] used;

    public int reletive_7 (int[] digit) {
        int length = digit.length, res = 0;
        used = new boolean[length];

        for (int i = 0; i < length; i++) {
            dfs(digit, i, length, 1, 0);
        }

        for (int i : list) {
            if (i % 7 == 0) {
                res++;
            }
        }

        return res;
    }

    public void dfs (int[] digit, int i, int length, int now, int number) {
        used[i] = true;

        number = number * 10 + digit[i];
        if (now == length) {
            list.add(number);
            used[i] = false;
            return;
        }

        for (int j = 0; j < length; j++) {
            if (!used[j]) {
                dfs(digit, j, length, now + 1, number);
            }
        }

        used[i] = false;
    }
}