万州网站制作公司,wordpress修改网站地址,网络优化软件下载,国外网站设计公司题目描述
小明是一位科学家#xff0c;他需要参加一场重要的国际科学大会#xff0c;以展示自己的最新研究成果。他需要带一些研究材料#xff0c;但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等#xff0c;它们各自占据不同的空间#xff0…题目描述
小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。
小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。
输入描述
第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。
第二行包含 M 个正整数代表每种研究材料的所占空间。
第三行包含 M 个正整数代表每种研究材料的价值。
输出描述
输出一个整数代表小明能够携带的研究材料的最大价值。
输入示例
6 1
2 2 3 1 5 2
2 3 1 5 4 3
输出示例
5
提示信息
小明能够携带 6 种研究材料但是行李空间只有 1而占用空间为 1 的研究材料价值为 5所以最终答案输出 5。
数据范围 1 N 5000 1 M 5000 研究材料占用空间和价值都小于等于 1000 思路
本题是一个 0/1 背包问题。可以采用动态规划解决。dp[ i ][ j ] 表示 0~ i 号物品放入 容量为 j 的背包时的最大价值。
确定递推公式dp[ i ][ j ] 有两个来源
容量为 j 的背包不能装下 i 号物品则容量为 j 的背包中所装的物品为 0 ~ i-1 号其最大价值为 dp [ i -1 ][ j ] 容量为 j 的背包能装下 i 号物品则容量为 j 的背包 此时所能装下的价值为 dp[ i-1 ][ j - weight [ i ] ] value[ i ]
故 dp[ i ][ j ] Math.max(dp [ i -1 ][ j ] dp[ i-1 ][ j - weight [ i ] ] value[ i ]);
初始化当容量 j 0 时 dp[ i ][ 0 ] 肯定为 0当 i 0即只将 0 号物品装入 背包时如果背包的容量 j weight [ 0 ]则此时装不进背包背包中的价值为 0当 背包的容量 j weight[ 0] 时这时可以将 0 号物品装入背包背包的价值为 value[ 0 ]。
遍历顺序从 i 1j 1 开始从左往右从上往下遍历因为从递推公式来看 dp[ i ][ j ] 依赖其左上方 的 dp 值。
代码
import java.util.*;
class Main{public static void main(String [] args){Scanner scan new Scanner(System.in);int m scan.nextInt();int n scan.nextInt(); //背包大小int[] weight new int[m];int[] value new int[m];for(int i0;im;i){weight[i] scan.nextInt();}for(int i0;im;i){value[i] scan.nextInt();}// dp[i][j] 表示 0到 i 号物品 放在容量为 j 的背包里面的最大价值int [][] dp new int[m][n1];// 对 dp 进行初始化for(int jweight[0];jn1;j){dp[0][j] value[0];}for(int i1;im;i){for(int j1;jn1;j){dp[i][j] Math.max(dp[i-1][j],(j-weight[i]0)?dp[i-1][j-weight[i]]value[i]:-1);}}System.out.println(dp[m-1][n]);}
}
参考代码随想录
