algorithm - 算法找到最有值(value)的组合？

我正在做一个小项目，在这个项目中，我需要帮助，根据用户的一些输入，找到最好、最便宜的门票：
在什么时间段（开始和结束日期）之间？
在这段时间里，你会跳过一次或几次约会吗？
你每天要用几次票？
有X张票。一张票可以包括：
单程票，只使用一次，价格5美元。
定期票（每天不限乘车次数），从1天/10美元、3天/30美元、7天/45美元起任意使用。
我想我在寻找一种算法，根据时段（包括或不包括跳过日期）以及票价来确定机票的最佳组合。
另外，我想有必要考虑这样一种情况：对于我来说，购买一张涵盖比我实际需要的更多天的定期车票会是一个更好、更便宜的结果，但是根据我每天要乘坐多少次的车次来看会更便宜……
更新（基于Petr建议…）

<?php


$tickets = array(
    array("price"=>5, "label"=>"single", "period"=>null),
    array("price"=>10, "label"=>"1 day", "period"=>1),
    array("price"=>30, "label"=>"3 days", "period"=>3),
    array("price"=>45, "label"=>"7 days", "period"=>7)
);

$trips = 2;
$startDate = new DateTime("2015-06-23");
$endDate = new DateTime("2015-06-30");
$endDate->modify("+1 day");

$interval = DateInterval::createFromDateString('1 day');
$period = new DatePeriod($startDate, $interval, $endDate);

$cost = array();
$day = 1;

foreach( $period as $date ){
    $span = $startDate->diff($date);
    $days = ( $span->format('%a') + 1 );

    $ticket = getCheapestTicket( $days );
    $cost[ $day ] = $ticket;

    $day++;
}


function getCheapestTicket( $days ){
    global $tickets, $trips;

    $lowestSum = null;
    $cheapestTicket = null;

    echo "-- getCheapestTicket --" . PHP_EOL;
    echo "DAYS TO COVER: " . $days . " / TRIPS: " . $trips . PHP_EOL;

    foreach( $tickets as $ticket ){
        $price = $ticket['price'];
        $period = $ticket['period'] ? $ticket['period'] : -1;

        if( $ticket['period'] ){
            $units = ceil( $days / $period );
            $sum = round( $units * $price );
        }else{
            $units = ceil( $days * $trips );
            $sum = round( ( $days * $price ) * $trips );
        }

        if( $sum <= $lowestSum || !$lowestSum ){

            if( $ticket['period'] > $cheapestTicket['period'] ){
                $cheapestTicket = $ticket;
                $lowestSum = $sum;
            }else{
                $lowestSum = $sum;
                $cheapestTicket = $ticket;
            }

        }

        echo "TICKET: " . $ticket['label'] . " / Units to cover days: " . $units . " / Sum: " . $sum . " / Period: " . $period . PHP_EOL;
    }

    echo "CHEAPEST TICKET: " . $cheapestTicket['label'] .
    " / PRICE PER UNIT: " . $cheapestTicket['price'] . " / SUM: " . $lowestSum . PHP_EOL. PHP_EOL;

    return $cheapestTicket;

}

我不确定这是否在路上：）

最佳答案

假设您将所有数据存储在某个日期数组中，并且每天都记下当天的乘车次数。
旁注：我将放宽24小时定期票的条件，并假设每一张定期票在该日期有效（即，不从15:00开始，持续到第二天14:59）。这可以通过将其视为小时时间单位而不是天来解决。
次优解：
现在，让我们将购买当天一张车票的成本分配给所有天，然后开始遍历数组并检查是否可以用更便宜的车票替换其中的一些车票当没有做任何更改时完成这里的问题是你可能会错过最佳的解决方案您可以指定两张3天的票（1-3天和7-9天），其中7天的票（2-8天）和两张1天的票会更好。
树解决方案：（叶中的数据）
树选项是将其排列在一棵树中，每个子树包含该子树的最佳解决方案。然后，每个子树根可以检查在考虑遗漏部分的根的值时，使用票据“覆盖”子树的一部分是否有用。
也许排名树在这里会派上用场。