笔试共三道编程题（全部ac）,该题为第三题，第二题为牛客上剑指offer的第33题，我的博客上也有，第一题太简单就不记录了。
问题类型：0-1背包问题
解决：动态规划+递归思想
ac:100%
题目描述：
一个人背包能装一定重量的物品，现在这里有n件物品，每个物品有固定的重量和价值，如何在不超过背包能做装的总重量下的情况下，获得价值最大的物品。
输入：
第一行，物品数量n
第二行：背包能装最大重量m
第三行：每个物品的重量
第四行：每个物品的价值
输出：
最大价值
样例输入：
5
10
2 2 6 5 4
6 3 5 4 6
样例输出：
15
import java.util.Scanner;public class Third {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] thing = new int[2][n];for(int x = 0; x < 2; x++) {for(int i = 0; i < n; i++) {thing[x][i] = sc.nextInt();//0:重量；1：价值}}//dp[i][j]当背包容量为j的时候，选取前i件商品，最大价值为dp[i][j]int[][] dp = new int[n + 1][m + 1];//为每一行赋值j:容量；i:前i件商品for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {//当前商品重量大于jif(thing[0][i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {//当前商品重量小于jdp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][(j - thing[0][i - 1])] + thing[1][i - 1]);//--dp[i][j] = max(//dp[i - 1][j]//dp[i - 1][j - thing[0][i - 1] + thing[1][i - 1]//)}}}System.out.println(dp[n][m]);}}
