首页 > 17号晚上vivo提前批的笔试第二题疑问
头像
loovi7
编辑于 2021-06-18 14:13
+ 关注

17号晚上vivo提前批的笔试第二题疑问

输入有啥更好的处理方法吗

要求输入三行
第一行:背包最大重量
第二行:所有货品重量,逗号隔开
第三行:所有货品价值,逗号隔开
处理二三行的方式,我是先用scanner.next()获取整行,然后split(",")得到字符串数组,然后再遍历,用Integer.valueOf()获取对应的整型。这么做是不是太麻烦了?有快一点的方法吗?求助。
引流:阿里 腾讯 美团 字节 华为

/*
* vivo笔试题2:01背包问题
* 货轮最大容量C,货品重量数组w[],货品价值数组v[]
* 求最大载货价值
*
* 解:dp[i][j] 表示从下标为[0-i]的物品⾥任意取,放进容量为j的背包,价值总和最⼤是多少
* 可以有两个⽅向推出来dp[i][j],
    1.由dp[i - 1][j]推出,即背包容量为j,⾥⾯不放物品i的最⼤价值,此时dp[i][j]就是dp[i - 1][j]
    2.由dp[i - 1][j - weight[i]]推出, dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最⼤价值,那么dp[i - 1][j - weight[i]] + value[i] (物品i的价值),就是背包放物品i得到的最⼤价值
* 所以递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
* */
package com.luowei.exam.vivo;
import java.util.Scanner;
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt();
        String[] weight = sc.next().split(",");
        String[] value = sc.next().split(",");
        int n = weight.length;
        int[] w = new int[n];
        int[] v = new int[n];
        for(int i = 0; i < n; i++){
            w[i] = Integer.valueOf(weight[i]);
            v[i] = Integer.valueOf(value[i]);
        }

        int[][] ans = packtrack(c, n, w, v);
        System.out.println(ans[n-1][c]);
    }

    public static int[][] packtrack(int c, int n, int[] w, int[] v){//背包问题的表
        int[][] dp = new int[n][c+1];
        for(int j = c; j >= w[0]; j--){
            dp[0][j] = dp[0][j - w[0]] + v[0];
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < c+1; j++){
                if(w[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        return dp;
    }
}

全部评论

(14) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐