当前位置: 首页 > article >正文

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

🍎笔记
在这里插入图片描述
在这里插入图片描述


http://www.kler.cn/a/588474.html

相关文章:

  • NocoBase 本周更新汇总:双因素身份认证(2FA)
  • 蓝桥杯学习-08序列二分
  • 【动手学深度学习】#2线性神经网络
  • 火焰图分析Java程序瓶颈
  • 第15章:ConvNeXt图像分类实战:遥感场景分类【包含本地网页部署、迁移学习】
  • git subtree在本地合并子仓库到主仓库
  • KY-038 声音传感器如何工作以及如何将其与 ESP32 连接
  • java 线程池Executor框架
  • 深入解析 Vue 3 Teleport:原理、应用与最佳实践
  • 使用Inno Setup将Unity程序打成一个安装包
  • Native层逆向:ARM汇编与JNI调用分析
  • node.js-WebScoket心跳机制(服务器定时发送数据,检测连接状态,重连)
  • 游戏成瘾与学习动力激发策略研究——自我效能理论
  • 深入理解Linux网络随笔(七):容器网络虚拟化--Veth设备对
  • 基于javaweb的SSM+Maven网上选课管理系统设计与实现(源码+文档+部署讲解)
  • JavaScript性能优化的12种方式
  • Function 和 Consumer函数式接口
  • Ubuntu docker镜像恢复至原始文件
  • React使用路由表
  • 使用GoldenGate完成SQLserver到Oracle的数据实时同步