程序员经验分享-hwhale

如何确定最便宜的通勤票组合

2023-12-22

My 当地火车服务 http://www.sunrail.com/default.aspx?faresandpasses/reloadable.htm最近添加了日常通勤的选项。我正在尝试确定一种算法，用于查找给定日期的一组给定往返行程的最便宜的机票组合。

这里是英语的问题。给定一组天数和每天的乘车次数，以下组合是最便宜的。

  • 往返票价一张w每次往返。
  • 7天票价x连续 7 个日历日内无限次乘坐。
  • 30 天的票价y连续 30 个日历日内无限次乘坐。
  • 365 天的票价z连续 365 个日历日内无限次乘坐。

由于我很乐意将其限制为一次只能求解一年，因此我认为天数列表可以轻松存储在如下所示的数组中。

{0,0,1,1,1,0,0,2,1,0,0,0,4,0,1,1,...,0,1,1,5}

其中数量等于每天的往返次数。

我可以使用什么算法来确定涵盖所有行程的最便宜的机票组合？


Hints

您可以通过解决子问题来做到这一点：

What is the cheapest combination C[k] to cover all trips from day 0 up to day k?

要计算此子问题的答案，您可以简单地考虑购买门票类型的每种情况。通过解决从 0 开始一直到 365 的问题，您可以在解决子问题时使用以前的结果。

例如，假设在第 100 天您无需出行。那么答案将是 C[99]，这是前几天行程最便宜的方式。

然而，假设在第 101 天您需要进行 3 次旅行。那么 C[101] 的答案将是最便宜的：

Buy round trip tickets today: cost 3*w+C[100]
Buy a 7 day ticket 7 days ago: cost x+C[101-7]
Buy a 30 day ticket 30 days ago: cost y+C[101-30]

当您计算出 C[365] 后，您可以将其与全年门票的成本 z 进行比较。

（如果在此过程中您发现自己需要 i 小于 0 的成本 C[i]，则 C[i] 的值为 0。）

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

dynamicprogramming

knapsackproblem

如何确定最便宜的通勤票组合 的相关文章

  • 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的差异

    我最近偶然发现了一个资源 其中 2T n 2 n log ntypeMM 宣布复发无法解决 我接受它作为一个引理 直到今天 另一种资源被证明是矛盾的 在某种意义上 根据资源 下面的链接 其中的 Q7 和 Q18 是建议 分别在问题中的1和2

  • 由周期表元素形成的最大单词的算法

    我想为以下问题场景编写一个算法 根据元素周期表元素的名称 找到可以组成的最大单词 符号如Na Ne等应被视为单个元素 这是在一家知名公司的求职面试中被问到的 有人可以帮我解决这个问题吗 我认为更好的方法是检查字典中的每个单词 看看是否可以从

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • 关于在字典中查找所有有效单词的算法问题

    给定一个字典 只是一个字符串列表 您收到来自外部来源的未知数量的信件 给定字母串 您将如何列出您可以通过这些字母的任意组合组成的所有有效单词 来自字典 因此 如果您收到 applead 你应该找到apple bad pad lead等 我知

  • 分而治之策略来确定列表中是否有超过 1/3 的相同元素

    我正在使用分治算法来确定列表中是否有超过 1 3 的元素相同 例如 1 2 3 4 不 所有元素都是唯一的 1 1 2 4 5 是的 其中 2 个是相同的 没有排序 是否有分而治之的策略 我陷入了如何划分的困境 def is valid i

  • 带路径压缩算法的加权 Quick-Union

    有一种 带路径压缩的加权快速联合 算法 代码 public class WeightedQU private int id private int iz public WeightedQU int N id new int N iz new

  • 用 C++ 生成 AST

    我正在用 C 制作一个解释器 到目前为止我已经有了词法分析器来生成标记 问题是我不确定如何生成 行走 解析树 我正在考虑使用数组数组来制作解析树 但我不确定如何以正确的顺序将标记实际插入到解析树中 我不确定是自上而下 左右还是自下而上 左右

  • 异或交换可以扩展到两个以上的变量吗？

    我一直在尝试将异或交换扩展到两个以上的变量 例如n变量 但我没有得到比这更好的地方3 n 1 对于两个整型变量x1 and x2你可以像这样交换它们 swap x1 x2 x1 x1 x2 x2 x1 x2 x1 x1 x2 所以 假设你有

  • 使用并集查找（又名不相交集）检测图是否是二分图

    我正在 Spoj 上做一个问题 基本上可以简化为检测图是否是二分图 我正在尝试使用 dfs 为图表着色 但它太慢了 有人评论这个 没有 bfs 没有 dfs 没有二部图 简单的并查集就可以做到 确实速度很快 提示 1 偶数长度的环不会影响两

  • 计算两点之间的最短路线

    过去几周我一直在开发一款多人 HTML5 游戏 使用nodejs and websockets 我已经被这个问题困扰了一段时间 想象一下 我用数组实现了这个平铺地图 如下所示 1 or 棕色瓷砖 路上有障碍物 玩家无法通过 0 or 绿色瓷

  • 迭代任意大小的子集

    我可以迭代大小为 1 的子集 for int a 0 a lt size a 或大小为 2 的子集 for int a1 0 a1 lt size a1 for int a2 a1 1 a2 lt size a2 or 3 for int

  • Florian 的 Grisu2 算法如何工作？

    我遇到了一个关于将 double 转换为 ascii 的问题 经过搜索 我得到了 Florian 的论文 使用整数快速准确地打印浮点数 http www cs tufts edu nr cs257 archive florian loits

  • 大数据使用什么数据结构

    我有一个包含一百万行的 Excel 工作表 每行有 100 列 每行代表一个具有 100 个属性的类的实例 列值是这些属性的值 哪种数据结构最适合在这里使用来存储数百万个数据实例 Thanks 这实际上取决于您需要如何访问这些数据以及您想要

  • 在 O(n) 时间内排序？

    我被这个问题困扰了 2周 知道如何处理它吗 令 L 为 n 个不同整数的列表 假设 L 的 x 的元素在 1 750 范围内 设计线性排序算法对 L 的元素进行排序 我已经尝试过插入排序 但我不确定我的方法是否正确 Construct an

  • 两组点之间的最佳匹配

    I ve got two lists of points let s call them L1 P1 x1 y1 Pn xn yn and L2 P 1 x 1 y 1 P n x n y n 我的任务是找到它们点之间的最佳匹配 以最小化它

  • 举例解释bpe（字节对编码）？

    有人可以帮忙解释一下背后的基本概念吗BPE模型 除了这张纸 https arxiv org abs 1508 07909 目前还没有那么多解释 到目前为止我所知道的是 它通过将罕见和未知的单词编码为子词单元序列来实现开放词汇表上的 NMT

  • Java递归方法求阶乘返回负输出[重复]

    这个问题在这里已经有答案了 我知道这是溢出 但问题是 20 是相对较小的数字 这不应该发生 对吧 有没有更好的方法来查找大数 例如 1000 的阶乘 而不会得到这种奇怪的结果 public class RecursiveFunctionsE

  • 照片马赛克算法。如何在给定基本图像和瓷砖列表的情况下创建马赛克照片？

    Hy 我要做的是创建一个程序 使用 C 或 C 它将 24 位 像素位图和图像集合作为输入 我必须创建一个马赛克图像 类似于使用库的输入图像给定的图像 创建与输入类似的马赛克照片 到目前为止 我可以访问输入的图像像素及其颜色 但我有点卡住了

  • O(1) 算法确定节点是否是多路树中另一个节点的后代？

    想象一下下面的树 A B C D E F 我正在寻找一种方法来查询 F 是否是 A 的后代 注意 F 不需要是directA 的后代 在这种特殊情况下这是正确的 只需要针对更大的潜在后代节点池测试有限数量的潜在父节点 当测试一个节点是否是潜

  • Prim 的迷宫生成算法：获取相邻单元格

    我基于 Prim 算法编写了一个迷宫生成器程序 该算法是 Prim 算法的随机版本 从充满墙壁的网格开始 选择一个单元格 将其标记为迷宫的一部分 将单元格的墙壁添加到墙壁列表中 While there are walls in the li

随机推荐

  • 使用匿名类型集合填充 WPF 中的 DataGrid

    我正在使用匿名类型的集合填充数据网格 我正在设置DataGrid s DataContext财产 并且没有错误 数据网格中没有显示任何内容 我尝试对定义的对象集合进行相同的操作 但再次没有显示任何内容 请您指导我该怎么做 Thanks ED

  • 奇怪的“字符串索引超出范围：0”错误

    我有一个巨大的应用程序 在某些时候 当涉及重定向时 我收到了这个奇怪的错误 Caused by java lang StringIndexOutOfBoundsException with message String index out

  • 编写电子邮件嗅探器

    我有兴趣编写一个电子邮件嗅探器 将通过基于网络的客户端发送的所有电子邮件保存到高清 但我不知道如何做到这一点 如何在加密之前捕获 HTTPS 邮件 我真的很感激一些有用的信息 我在网上找不到任何信息 有一个名为 HTTP Analyzer

  • 是否有 shim 或 polyfill 可以解决 Chrome 对数据列表的 512 限制？

    使用绑定到数据列表的输入标签实现了预输入 当用户滚动浏览条目时 Chrome 不会显示第 512 个匹配项之外的任何条目 整个数据列表仅包含大约 950 个条目 使用适用于 Windows 的 Chrome 版本 76 0 3809 100

  • 在大表中查找半径MySQL（纬度经度）内的点的最快方法是什么

    目前我有几个包含 100k 行的表 我正在尝试查找如下数据 SELECT SQRT POW 69 1 latitude 49 1044302 2 POW 69 1 122 801094 longitude COS latitude 57 3

  • ng-click 和 ng-touch 移动设备

    我有一个用 AngularJS 编写的 cordova 移动应用程序 在我的应用程序中添加 ng touch 会使某些 html 行为无法正常工作 此问题的一个示例是 当复选框包装在附有 ng click 的 HTML 元素中时 该复选框不

  • 隐藏的表单元素是否被提交？

    如果 jQuery 的toggle 用于 div 包含表单元素 这些表单元素是否会随表单一起提交 即使它们是隐藏的 我的代码 尽管这个特定问题可能不需要 cms loop title click function ctg this attr

  • 使用 C 的原始 libcurl JSON PUT 请求

    我目前正在编写一个类似 REST 的客户端 只需要执行 PUT 请求 Problem 运行该程序并没有在 URL 的 API 上给出正确的结果 我不知道为什么 使用curl easy perform curl 在调用时不会抛出错误 但 UR

  • 我应该在哪里设置 DataContext - 代码隐藏或 xaml？

    老实说 我搜索并阅读了所有似乎相关的 相关问题 我确实希望我没有 错过 其他地方的这个问题 但这里是 至少 有两种不同的方法来设置 DataContext 可以使用 XAML 也可以使用隐藏代码 什么是 最佳实践 为什么 我倾向于在 XAM

  • 如何在 MongoDB 上模拟“错误”事件

    我正在尝试为 NoFlo 组件 由同事编写 编写一个测试用例 该组件有一个 连接 输入端口和一个 错误 输出端口 例如 var self this a NoFlo Component var mongodb null self inPort

  • Meteor 允许更新插入吗？

    当我尝试更新插入集合时 在控制台中出现此错误 更新失败 访问被拒绝 受限集合中不允许更新插入 以下是我指定的允许规则 if Meteor isClient Meteor subscribe customers customers Custo

  • WinForms - Form.DoubleBuffered 属性是否影响放置在该窗体上的控件？

    Form具有 DoubleBuffered 属性 布尔值 继承自 Control 如果将此设置为 true 则放置在窗体上的所有控件是否都会由于位于窗体上而以双缓冲方式绘制到屏幕上 或者您需要担心它们自己的 DoubleBuffered 属

  • 混合托管/非托管 C++？

    我有一个用标准 C 编写的库 我还有一个用 C 编写的 Net Windows 窗体应用程序 它利用非托管库 我知道我可以只使用 pinvoke 但我的 C 完全是面向对象的 我真的不想乱搞编组等 有没有一种方法可以让我创建一个新的托管 C

  • codeigniter 的自定义配置文件

    对 CodeIgniter 非常陌生 尝试创建自定义配置文件以将特殊变量加载到我的应用程序中 in application config 我创建custom php并将以下代码放入该文件中 然后我就打开了application config

  • 在第三方、非 AMD 库中使用 AMD 定义的模块

    我有一个图书馆 叫它SomeLib 定义为支持各种模块加载器 function global factory if typeof define function define amd define factory else if typeo

  • 可以对 header(Location: value) 中的值进行 urlencode 吗？

    这是PHP I do header Location url 并且效果很好 但如果我这样做 header Location urlencode url 我被重定向到一些奇怪的地方 比如 url url 当然 它给了我一个 404 错误 但我

  • 这会导致万向节锁定吗？

    我制作了一个非常简单的 3D 场景 在世界坐标中有 5 个点 我想在场景中导航 因此我定义了一个具有 UP 和 OUT 向量的相机 有了这些信息 我在每一帧中生成一个旋转矩阵 我将其应用于向量以获得相机坐标 问题是 我已经读到使用此方法时会

  • 比较两个枚举*类型*的等价性？

    在我的应用程序中 我有两个等效的enums 一个位于 DAL 中 另一个位于服务契约层中 它们具有相同的名称 但位于不同的命名空间中 并且应该具有相同的成员和值 我想编写一个单元测试来强制执行此操作 到目前为止 我已经得到以下内容 publ

  • 在 Node.js 中读取 PNG 图像

    Node js 中有没有一种简单的方法来读取 PNG 文件并获取图像的像素 就像是节点图像 https github com pkrumins node image 但另一种方式 我浏览了列出的图书馆https github com joy

  • 如何确定最便宜的通勤票组合

    My 当地火车服务 http www sunrail com default aspx faresandpasses reloadable htm最近添加了日常通勤的选项 我正在尝试确定一种算法 用于查找给定日期的一组给定往返行程的最便宜的

热门标签