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

本文介绍了如何确定最便宜的通勤票组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我的本地火车服务最近添加了一种用于通勤的选项。我正在尝试确定用于在给定日期的给定往返行程中找到最便宜的机票组合的算法。

My local train service recently added an option for dialy commute. I am trying to determine the algorithm for finding the cheapest combination of tickets for a given set of round trips on given days.

这是英语中的问题。给定一组天数和每天的行驶次数，以下几种组合最便宜。

Here is the problem in english. Given a set of days and and rides per day what combination of the following is the cheapest.

• 往返机票，每次往返费用为 w 。
• 连续7个日历日可无限次乘车的7天门票，价格为 x 。
• 30天的门票，价格为 y
• 一张365天的票，价格为 z ，可连续365个日历日无限次乘坐。

• A round trip ticket at cost w per round trip.
• A 7 day ticket at cost x for unlimited rides during 7 consecutive calendar days.
• A 30 day ticket at cost y for unlimited rides during 30 consecutive calendar days.
• A 365 day ticket at cost z for unlimited rides during 365 consecutive calendar days.

由于我很乐意将其限制为一次只能解决一年，因此我认为可以将日期列表轻松地存储在一个看起来像

Since I am happy to restrict this to only solving for one year at a time, I think that the list of days could easily be stored in an array that looks something like this.

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

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

Where the number is equal to the number of round trips per day.

p>

推荐答案

提示

您可以通过解决b问题：

Hints

You can do this by solving the sub-problem:

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

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

To compute the answer to this sub-problem you can simply consider each of the cases of buying a ticket type. By solving the problems starting at 0 and working all the way up to 365 you are allowed to use previous results when solving a sub-problem.

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

For example, suppose on day 100 you need to make no trips. Then the answer will be C[99] which is the cheapest way of doing the trips on the previous days.

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

However, suppose on day 101 you need to make 3 trips. Then the answer for C[101] will be the cheapest of:

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进行比较。

When you have computed C[365] you can compare this to cost z for the all year ticket.

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

(If during this process you ever find yourself requiring the cost C[i] for i less than 0, the value of C[i] is 0.)