假期和假期如何最大限度地利用假期？

Question

這是更多的算法評論： -

問題：給定假期爲整數列表，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; 
} 

Answer 1

這是一個使用聯邦假日東西在哈斯克爾（一月1-20在列表的末尾，以便該計劃將利用在節日的子序列的建設寒假）。它會輸出X個假期中最長或最短的總休假日，利用N或更少的休假天數 - 這些假期中的很多都是一天假（但可能有假期可用來補充它們）。如果您正在尋找X假期中最短的最短假期，則可能需要進行一些調整。這是一個過濾最多的組合方法。

方法：

1. 節假日列出所有的子序列。

2. 形式從1

3. 濾波器的子序列的X數目的所有組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)