题目链接
P1048 [NOIP2005 普及组] 采药
题目描述
实现代码
思路:每一个草药都有两种选择:采或者不采,因此可以通过DFS的形式对这两种选择进行比较去最优解;
采用DFS的形式实现:
import java.util.Scanner;
/**
* @Description:
* @Author: JreamY
* @Date: 2022/2/25
**/
public class Demo {
static int result = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt(); // 总采药时间
int M = in.nextInt(); // 草药总数
int[] times = new int[M + 1];
int[] values = new int[M + 1];
for (int i = 1; i <= M; i++) {
times[i] = in.nextInt();
values[i] = in.nextInt();
}
in.close();
dfs(1, T, M, times, values, 0);
System.out.println(result);
}
public static void dfs(int pos, int T, int M, int[] times, int[] values, int res) {
if (pos == M + 1) {
result = (result > res ? result : res);
return;
}
if (T < 0) {
return;
}
// pos位置的药采
dfs(pos + 1, T, M, times, values, res);
// pos位置的药不采
dfs(pos + 1, T - times[pos], M, times, values, res + values[pos]);
}
}
进一步简化dfs,使其变成有返回的方法:
package ccnu.agile.jdk8;
import java.util.Scanner;
/**
* @Description:
* @Author: JreamY
* @Date: 2022/2/25
**/
public class Demo {
static int result = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt(); // 总采药时间
int M = in.nextInt(); // 草药总数
int[] times = new int[M + 1];
int[] values = new int[M + 1];
for (int i = 1; i <= M; i++) {
times[i] = in.nextInt();
values[i] = in.nextInt();
}
in.close();
System.out.println(dfs2(1, T, M, times, values));
}
public static int dfs2(int pos, int T, int M, int[] times, int[] values) {
if (pos == M + 1) {
return 0;
}
int unUseResult, useResult = Integer.MIN_VALUE;
unUseResult = dfs2(pos + 1, T, M, times, values);
if (T >= times[pos]) {
useResult = dfs2(pos + 1, T - times[pos], M, times, values) + values[pos];
}
return Math.max(useResult, unUseResult);
}
}
在dfs递归过程中做了很多重复的dfs操作,因此可以通过标记将已经做过操作的保存起来,查询条件为:pos + T:
package ccnu.agile.jdk8;
import java.util.Scanner;
/**
* @Description:
* @Author: JreamY
* @Date: 2022/2/25
**/
public class Demo {
static int result = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt(); // 总采药时间
int M = in.nextInt(); // 草药总数
int[] times = new int[M + 1];
int[] values = new int[M + 1];
for (int i = 1; i <= M; i++) {
times[i] = in.nextInt();
values[i] = in.nextInt();
}
in.close();
int[][] mem = new int[M+2][T+1];
for(int i=1; i<=M+1; i++) {
for(int j=1; j<=T; j++) {
mem[i][j] = -1;
}
}
System.out.println(dfs3(1, T, M, times, values, mem));
}
public static int dfs3(int pos, int T, int M, int[] times, int[] values, int[][] mem) {
if(mem[pos][T] != -1) {
return mem[pos][T];
}
if (pos == M + 1) {
return mem[pos][T] = 0;
}
int unUseResult, useResult = Integer.MIN_VALUE;
unUseResult = dfs3(pos + 1, T, M, times, values, mem);
if (T >= times[pos]) {
useResult = dfs3(pos + 1, T - times[pos], M, times, values, mem) + values[pos];
}
return mem[pos][T] = Math.max(useResult, unUseResult);
}
}
进一步的来看,可以发现,每一步的结果可以通过已经得到的结果进行表示,即DP,对应的状态转移方程为:
mem[pos][T] = max(mem[pos+1][T], mem[pos+1][T-times[pos]] + values[pos]);