经典背包问题

import java.io.*;

public class Main {
	static BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	public static void main(String[] args) throws IOException,NullPointerException {
	        //获取T和M
		String[] temp=bf.readLine().split(" ");
		int T=Integer.parseInt(temp[0]);
		int M=Integer.parseInt(temp[1]);
		//开创时间容量数组，和价值数组
		int[] timeArr=new int[M+1];
		int[] valueArr=new int[M+1];
		//存入数据
		for(int i=1;i<=M;i++) {
			temp=bf.readLine().split(" ");
			timeArr[i]=Integer.parseInt(temp[0]);
			valueArr[i]=Integer.parseInt(temp[1]);
		}
		//设一个dp数组
		int[][] dp=new int[M+1][T+1];
		//遍历M件物品
		for(int i=1;i<=M;i++) {
		        //遍历每件物品的体积，取得各个体积的最大价值
			for(int j=T;j>=0;j--) {
				if(j>=timeArr[i]) {
					dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-timeArr[i]]+valueArr[i]);
				}else {
					dp[i][j]=dp[i-1][j];
				}
			}
		}
		//输出当时间取T时，且遍历完M件物品时的价值
		pw.print(dp[M][T]);
		pw.flush();
	}
	
}

解题思路:
    水平不够，没有再去理解一维动态规划的解法，但是也差不多了，没啥区别的，这里省事方便理解就用二维了

    非常经典的背包问题，首先用快读快写存入数据，也就是一个模板，背下来非常方便，然后遍历遍历M件物品，i为何止，代表着，当前可以选前i件物品，在循环体积，j为何值，dp[i][j]的意思即为，在前i件物品中选，体积为j时的最大价值，如果选了，那么说明前i-1件就只能有j-timeArr[i]的体积，也就是限定体积减去当前需要的体积，如果不选，那就直接取前i-1件，体积不变。如果当前限定的体积大于当前物品体积，那很明显，就不需要选当前这件，只有能选的时候才要判段。

    最后，获得前M件物品，设定体积为T，也就是题目要求的最大价值。

注意事项:
    物品从1开始记，注意初始化数组的长度