Java实现 藏宝架的宝物(分组DP,7.27阿里面试题)

时间:2020-7-30 作者:admin


有个藏宝架有n层,每层的宝物数量不一,每个宝物都有其价值,现在要求拿出m个宝物,并且需要遵守规则:
每次只能拿选定层的两端的宝物
要拿出的m个宝物的总价值是各种方案里最大的
输入:
n是层数,m是挑选的次数。n<=100,m<=10000
下面每行代表每层,且第一个数是这层宝物的数量k,后面的则是k个宝物的价值c

样例:
2 3
2 3 2
4 1 4 1 5
输出:10 

说明:
5+3+2=10
1<=n,k,c<=100
1<=m<=10000
输入保证宝物的数量够拿取的数量

大概思路:
先求每一行能拿i个宝物的最大值而且还要从两端开始拿 <=> 我们从中间取最小的一部分,然后用这一行所有宝物的和减去最小的这一小部分
然后每行的拿i个宝物的求出来了,然后在dp拼凑,求出最大的价值

import java.util.Scanner;

public class Demo222 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入n行的,并且取m个宝物
        int n = sc.nextInt();
        int m = sc.nextInt();
        //num[i][j]代表的是,第i行,取j个宝物的最大值
        int[][] num = new int[n][];
        int index = 0;
        //记录一下有几行宝物
        int maxSizeRow = n;
        //循环几行
        while (n-- > 0) {
            //输入当前行的宝物
            int len = sc.nextInt();
            int[] temp = new int[len];
            for (int i = 0; i < len; i++) {
                temp[i] = sc.nextInt();
            }
            //maxVal[i]表示取i个宝物的最大值
            int[] maxVal = new int[len + 1];
            int[] prevSum = new int[len];
            //求前缀和

            prevSum[0] = temp[0];   //附上初始值,第一个数的前缀和就是第一个数
            int sum = temp[0];
            for (int i = 1; i < len; i++) {
                prevSum[i] = prevSum[i - 1] + temp[i];
                sum += temp[i];
            }

            maxVal[len] = sum;      //把当前行所有的都拿了就是这些宝物的和
            /*
            * 这里用的思路为:
            *   我们取得话,只能拿两端得,要能拿到得最大值
            *   我们转换一下思路,我们只拿中间得最小值,那么剩下得就是最大值
            *
            * */

            for (int i = 1; i < len; i++) {     //取i个宝物
                int minVal = prevSum[i - 1];
                for (int j = 0; j < len - i; j++) {     //从j位置开始取
                    int k = i + j;                      //k为取得结束位置(从j位置取i个就是到i+j位置)
                    //找到中间最小得           这里就是最小的那一段得值
                    minVal = Math.min(minVal, prevSum[k] - prevSum[j]);
                }
                //我们取得是i个宝物得最小值,那么就是取(这一层的宝物数量-i)个最大值的宝物
                maxVal[len - i] = prevSum[len - 1] - minVal;
            }
            //放入我们的num数组,index是为了自动换行
            num[index++] = maxVal;

        }
        //dp[i][j]就是我们从头到i行取j个宝物的最大值
        int[][] dp = new int[maxSizeRow + 1][m + 1];
        for (int i = 1; i <= maxSizeRow; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k < num[i - 1].length && j - k >= 0; k++) {
                    //最大值就是上一层拿[j-k]个宝物这一层拿k个宝物(这里num[i-1]是因为我们的num是从第0行开始加入的)
                    dp[i][j] = Math.max(dp[i - 1][j - k] + num[i - 1][k], dp[i][j]);
                }
            }
        }
        System.out.println(dp[maxSizeRow][m]);


    }
}

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。