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)); // 记忆化搜索
    }
}

🍎笔记