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 日がリストの最後にあるため、プログラムは休日のサブシーケンスの構築に冬の休日を利用します)。N 日間以下の休暇を利用して、X 休暇の合計休暇日数の最長から最短までを出力します。これらの休暇の多くは 1 日です (ただし、休暇を追加して休暇を利用できる場合があります)。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 に答える