篮球队， 网易笔试题

篮球队， 网易笔试题

转化成01背包问题

设 目前有背包，共有n个商品，依次决定是否放入商品i,使得商品总价值达到指定指定数目。

定义，状态

f[i][j]表示前i个商品中，使背包中总价值为j的放置方案数量。

f[i][j]=f[i-1][j]+f[i-1][j-w[i]] if j >= w[i]

f[i][0]=1有前i个商品，使得商品总价值达到0的方案数为1。

f[0][0]=1,f[0][j]=0, j>0有0个商品，使得总价值大于0的方案数为0；

static long solution(Integer[] arr, int n, int sum) {
    long res = 0L;
    long[][] f = new long[n+1][sum+1]; 
    for(int i=0; i <= n; i++)
        f[i][0] = 1L;
    for(int j=1; j <= sum; j++)
        f[0][j] = 0L;
    for(int i=1; i <= n; i++) {
        int w = arr[i-1];
        for(int j=1; j <= sum; j++) {
            f[i][j] = f[i-1][j];
            if(j >= w) {
                f[i][j] += f[i-1][j-w];
                if(j != sum && j > sum-j && j-w < sum-j+w) {
                    res += f[i-1][j-w];
                }
            }
        }
    }
    return res;
}

60% 通过， 内存超限！！！

优化：

static long solution(Integer[] arr, int n, int sum) {
    long res = 0L;
    long[][] f = new long[2][sum+1]; 

    f[0][0] = 1L;
    for(int j=1; j <= sum; j++)
        f[0][j] = 0;
    for(int i=1; i <= n; i++) {
        int w = arr[i-1];
        for(int j=1; j <= sum; j++) {
            f[1][j] = f[0][j];
            if(j >= w) {
                f[1][j] += f[0][j-w];
                if(j != sum && j > sum-j && j-w < sum-j+w) {
                    res += f[0][j-w];
                }
            }
        }
        f[0][0] = 1L;
        for(int j=1; j <= sum; j++) f[0][j] = f[1][j];
    }
    return res;
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer[] w = new Integer[n];
    int sum = 0;
    for(int i=0; i < n; i++) {
        w[i] = sc.nextInt();
        sum += w[i];
    }
    Arrays.sort(w, (o1, o2)-> o2 - o1);
    long res = solution(w, n, sum);
    System.out.println(res);
}