KamaCoder 46. 携带研究材料（第六期模拟笔试）

题目描述

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 

小明的行李空间为 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 = 1，j = 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 i=0;i<m;i++){weight[i] = scan.nextInt();}for(int i=0;i<m;i++){value[i] = scan.nextInt();}// dp[i][j] 表示 0到 i 号物品 放在容量为 j 的背包里面的最大价值int [][] dp = new int[m][n+1];// 对 dp 进行初始化for(int j=weight[0];j<n+1;j++){dp[0][j] = value[0];}for(int i=1;i<m;i++){for(int j=1;j<n+1;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]);}
}

参考：代码随想录