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;
}
}
#笔经##vivo##笔试题目#
