阿里笔试7.27第二题多重背包解法

题干

有个藏宝架有n层，每层的宝物数量不一，每个宝物都有其价值，现在要求拿出m个宝物，并且需要遵守规则：

1. 每次只能拿选定层的两端的宝物
2. 要拿出的m个宝物的总价值是各种方案里最大的

输入：
n m
下面每行代表每层，且第一个数是这层宝物的数量k，后面的则是k个宝物的价值
4 1 2 4 5
5 1 2 4 5 5
样例：
2 3
2 3 2
4 1 4 1 5
输出：5+3+2=10

想了挺久，如有不足，希望各位大佬指正！

多重背包思路：

先用滑动窗口写一个函数getGoods遍历每一层物品，求出从该层取1 to n个物品可获得的最大价值。然后用多重背包的思路，其实就是将每层货架想象为一个物品，但取不同数量的物品价值是已经算好的。

代码

import java.util.Scanner;

public class T27_2 {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n_layer = sc.nextInt();
        int V = sc.nextInt();
        int[][] goods = new int[n_layer][];
        for (int i = 0; i < n_layer; i++){
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int j = 0; j < n; j++){
                arr[j] = sc.nextInt();
            }
            goods[i] = getGoods(arr);
        }
        int[] dp = new int[V+1];
        // muti-package
        for(int i = 0; i < n_layer; i++){
            for(int j = V; j >= 0; j--){
                for (int k = 0; k < goods[i].length && k <= j; k++){
                    dp[j] = Math.max(dp[j], dp[j - k] + goods[i][k]);
                }
            }
        }
        System.out.println(dp[V]);
    }

    private static int[] getGoods(int[] arr) {
        int sum = 0;
        int n = arr.length;
        for(int e : arr) sum += e;
        int[] res = new int[n + 1];
        res[n] = sum;
        for(int i = n-1; i > 0; i--){
            // i 表示从arr中选出i个物品
            // 用滑动窗口从中间删去不选的元素
            int start = 0;
            int end = n - i;
            int min = Integer.MAX_VALUE;
            while(end <= n){
                int tmp = 0;
                for(int j = start; j < end; j++){
                    tmp += arr[j];
                }
                min = Math.min(min, tmp);
                start++;
                end++;
            }
            res[i] = sum - min;
        }
        return res;

    }
}