题目链接：

Description

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

Input

输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

Output

输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

Sample Input

70 371 10069 11 2

Sample Output

3

HINT

对于30%的数据，M <= 10；

对于全部的数据，M <= 100。

分析?

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。

一共有M株草药，总共能够采摘的时间为T，每株草药的采摘时间为T1，T2至Tm，与之对应的价值为V1，V2至Vm。

value[i][j]表示在“选择”（选择不代表采摘）完第i株后，使用的总时间为j的情况下的总价值。

• 如果总时间j比采摘第i株的时间Ti还小的话，显然第i株不能采摘，因此选择完第i株后的总价值value[i][j]和选择完第i-1株后的总价值相同。即value[i][j]=value[i-1][j]
• 如果总时间j足够采摘第i株草药
  • 不采摘第i株后，总价值value[i][j]和选择完第i-1株后的总价值相同即value[i-1][j]
  • 采摘第i株后，总价值value[i][j]等于选择完第i-1株后的总价值加第i株的价值，即value[i-1][j-Ti]+Vi
  • 故，选择完第i株后的总价值value[i][j] = Math.max(value[i - 1][j], value[i - 1][j - Ti] + Vi)

示例：

输入

5 31 22 34 4

选择完后的value值如下：

	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	2	2	2	2	2
2	0	2	3	5	5	5
3	0	2	3	5	5	6

输出

6

代码?双重循环

/** * Time 500ms * @author wowpH * @version 1.2 * @date 2019年6月14日下午4:14:14 * Environment:	Windows 10 * IDE Version:	Eclipse 2019-3 * JDK Version:	JDK1.8.0_112 */import java.io.InputStreamReader;import java.util.Scanner;public class Main {
    	private Scanner sc = new Scanner(new InputStreamReader(System.in));	private int T, M;		// 总共能够用来采药的时间，山洞里的草药的数目	private Herb[] herbs;	// 草药，下标从1开始	private int[][] value;	// 采摘的草药的价值	public Main() {
    		while (sc.hasNext()) {
    			init();			System.out.println(solve());		}		sc.close();	}	private void init() {
    // 初始化		T = sc.nextInt();		M = sc.nextInt();		herbs = new Herb[M + 1];		herbs[0] = new Herb();		for (int i = 1; i <= M; ++i) {
    			herbs[i] = new Herb();			herbs[i].time = sc.nextInt();			herbs[i].value = sc.nextInt();		}		value = new int[M + 1][T + 1];	}	private int solve() {
    		int temp;		for (int i = 1; i <= M; ++i) {
    // M株草药			for (int j = 1; j <= T; ++j) {
    				if (j < herbs[i].time) {
    // 时间不够采摘第i株草药的情况					value[i][j] = value[i - 1][j];				} else {
    					// 采摘第i株草药后的价值					temp = value[i - 1][j - herbs[i].time] + herbs[i].value;					// 取“不采摘”和“采摘”第i株的价值较大的情况					value[i][j] = Math.max(value[i - 1][j], temp);				}			}		}		return value[M][T];// 返回最大价值	}	public static void main(String[] args) {
    		new Main();	}}class Herb {
    	int time;	// 采摘草药时间	int value;	// 草药的价值}

代码?递归

/** * Time 625ms * @author wowpH * @version 2.0 * @date 2019年6月15日下午9:52:12 * Environment:	Windows 10 * IDE Version:	Eclipse 2019-3 * JDK Version:	JDK1.8.0_112 */import java.io.InputStreamReader;import java.util.Scanner;public class Main {
    	private int[][] herbs, value;//草药，总价值	public Main() {
    		Scanner sc = new Scanner(new InputStreamReader(System.in));		int T, M;// 总共能够用来采药的时间，山洞里的草药的数目		while (sc.hasNext()) {
    			T = sc.nextInt();			M = sc.nextInt();			herbs = new int[M + 1][2];// 下标从1开始			for (int i = 1; i <= M; ++i) {
    				herbs[i][0] = sc.nextInt();// 时间				herbs[i][1] = sc.nextInt();// 价值			}			value = new int[M + 1][T + 1];			solve(M, T);			System.out.println(value[M][T]);		}		sc.close();	}	private void solve(int m, int t) {
    		if (m < 1) {
    // 递归结束条件			return;		}		if (herbs[m][0] > t) {
    // 时间不够			if (0 == value[m - 1][t]) {
    				solve(m - 1, t);// 选择前一株			}			value[m][t] = value[m - 1][t];// 和前一株价值相同		} else {
    // 时间够			// 不采摘第m株			if (0 == value[m - 1][t]) {
    // 前一株对应位置未计算过				solve(m - 1, t);// 递归选择前一株			}			// 采摘第m株			if (0 == value[m - 1][t - herbs[m][0]]) {
    // 没计算过				solve(m - 1, t - herbs[m][0]);// 递归计算			}			// 采摘后的值			int b = value[m - 1][t - herbs[m][0]] + herbs[m][1];			value[m][t] = Math.max(value[m - 1][t], b);// 取较大值		}	}	public static void main(String[] args) {
    		new Main();	}}

---

版权声明：

1. 转载请于首页注明链接形式的；
2. 代码原创，公开引用不能删除首行注释（作者，版本号，时间等信息）；
3. 如果有疑问欢迎评论区留言，尽量解答；
4. 如果有错误，还望大侠评论区指正。

---