输入有啥更好的处理方法吗
要求输入三行
第一行:背包最大重量
第二行:所有货品重量,逗号隔开
第三行:所有货品价值,逗号隔开
处理二三行的方式,我是先用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) 回帖