563采药
563采药
⭐️难度:困难
🌟考点:2005、动态规划、背包问题
📖
📚
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int t,m;
static int[][] dp ;
static int[] v ; // 每株草药所花费的时间
static int[] w; // 每株草药的价值
static int dfs(int u,int s){
if(u > m) return dp[u][s] = 0; // 如果超出,记录为0
if(dp[u][s] != -1) return dp[u][s]; // 如果dp不为-1,说明之前遍历过这种情况,直接返回记录的值
int ans1 = 0,ans2 = 0;
if(s + v[u] <= t){
ans1 = dfs(u + 1,s + v[u]) + w[u]; // 选择这株草药,继续遍历
}
ans2 = dfs(u + 1,s); // 不选这株草药,继续遍历
dp[u][s] = Math.max(ans1,ans2);
return dp[u][s];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
m = sc.nextInt();
dp = new int[110][1010];
v = new int[110]; // 每株草药所花费的时间
w = new int[110]; // 每株草药的价值
for (int i = 1; i <= m; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for (int i = 1; i <= m; i++) {
Arrays.fill(dp[i],-1); // 全部填充为-1
}
System.out.println(dfs(1,0)); // 记忆化搜索
}
}
🍎笔记