1

这更像是算法审查：-

问题：给定假期作为整数列表，介于 0-364 和可用的叶子数 N，如何最大化 X 假期中的天数，其中假期是一个日期范围，其中包含该范围内的假期和范围内的其余部分使用树叶。

我相信以下使用 getMaxVacations(X, 0, 364, N) 的伪代码可能适用于一些小的修复和优化，但我正在寻找其他方法来可视化问题，不一定更快。

available_leaves (N) = 5
holidays = [7, 14, 20, 21, 35, 36]

getMaxVacation (X, start, end, N) {
  if X = 0 return 0;
  for (d : end to start + 1) {
    for (leave : N to 1)
      total = bestSingleVacation(start, d, leave) + getMaxVacation(X-1, d, end, N-leave);
    if max < total
    max = total
  return max
}

bestSingleVacation(start, end, leaves_to_use) {
  maxVacationSize = leaves_to_use
  for (i : start; i < end-maxVacationSize; i++) {
    for (j : i ; j < leaves_to_use) {
      if (!holidays.contains(j)) j++; // use the leave
    }
    if (maxVacationSize < j-i) maxVacationSize = j-i;
  }
  return maxVacationSize;
}
4

1 回答 1

1

这是 Haskell 中使用联邦假期的东西（1 月 1 日至 20 日在列表的末尾，因此程序将利用寒假来构建假期子序列）。它将输出 X 个假期的总假期天数从最长到最短，使用 N 天或更少的假期 - 其中许多假期为一天（但假期可能会增加）。如果您正在寻找 X 假期中最长的最短假期，则可能需要进行一些调整。这是一种过滤的大多数组合方法。


方法：

  1. 列出假期的所有子序列。

  2. 从 1 形成所有 X 个子序列的组。

  3. 过滤 2. 使得中间天数（休假天数）不超过 N，并按休假天数降序返回它们。


N=15，X=4 的样本输出：

(17,[[1,15],[53],[150],[245]]) -17 days of vacation, 13 days of leave utilized
                                 for the first vacation 

(14,[[15,20],[53],[185],[359,1]]) -14 days of vacation, 10 days of leave utilized
                                   for the first and last vacation


程序代码：

import Control.Monad(guard)
import Data.List(sortBy, nub, intersect, sort, inits, tails)

federalHolidays = [53,150,185,245,285,315,332,359,1,15,20]
n = 15 --days of leave
x = 4 --number of vacations

differences xs = 
  sum $ map (\x -> x - 1) . tail 
  $ zipWith (\a b -> if a > b then a-b else a + 364 - b) xs ([0] ++ init xs)

countDays vacation = if null (drop 1 vacation) 
                        then 1 
                        else if last vacation > head vacation 
                                then last vacation - head vacation
                                else last vacation + 365 - head vacation

maxVacations = 
  sortBy (\a b -> compare (fst b) (fst a)) 
  $ zip (map (\x -> sum (map countDays x)) potentialVacations) 
  $ filter (\y -> sum (map differences y) <= n) potentialVacations
 where potentialVacations = nub (map sort $ solve [])
       holidaySubsequences = 
         filter (not . null) . concatMap inits . tails $ federalHolidays
       solve result = 
         if length result == x
            then [result]
            else do
              h <- holidaySubsequences
              guard (
                differences h <= n 
                && notElem h result 
                && all null (map (intersect h) result))
              solve (h:result)
于 2013-04-03T06:08:06.083 回答