C++で解く最大休暇日数の最大化問題｜動的計画法による実装例

問題概要

ある企業が、最も優秀な社員の一人に対して、リソース収集のためにN個の都市を巡る旅を与えることになりました。とはいえ、社員にも休暇は必要です。本問題では、特定の都市・特定の週でのみ休暇を取得できるという条件のもと、移動スケジュールを工夫して取得できる休暇日数を最大化することを目指します。ただし、以下のルールと制約を守る必要があります。

ルールと制約

• 移動範囲：移動できるのはN個の都市のみです（インデックスは0〜N-1）。最初は月曜日にインデックス0の都市にいます。
• フライト情報：都市同士はフライトで結ばれており、その状態はN×Nの行列flightsで表されます（必ずしも対称行列ではありません）。都市iから都市jへのフライトがない場合はflights[i][j]=0、ある場合は1となります。また、すべてのiについてflights[i][i]=0です。
• 旅行期間と移動制限：旅行できるのはK週間です。フライトは1日1回まで、かつ各週の月曜日の朝にしか利用できません。
• 休暇日数の制限：各都市で取得できる休暇日数は週ごとに異なり、N×Kの行列daysで表されます。days[i][j]は、第j週に都市iで取得できる最大休暇日数を示します。

つまり、flights行列とdays行列が与えられたとき、K週間の間に取得できる休暇日数の最大値を求めて出力するのが課題です。

入力例と出力例

たとえば、flights = [[0,1,1],[1,0,1],[1,1,0]]、days = [[1,3,1],[6,0,3],[3,3,3]] が入力された場合、出力は12になります。

このケースでは、第0週に都市1へ移動して6日間休み、第1週に都市2へ移動して3日間、第2週も都市2に滞在してさらに3日間の休暇を取ることで、合計12日という最大値が達成できます。

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を使うことで効率的に解けます。dp[i][j]を「第i週以降に都市jに滞在している場合に取得できる休暇日数の最大値」と定義します。後ろの週から順に計算していくことで、各週・各都市における最適な選択（そのまま滞在するか、フライトで別の都市へ移動するか）を決定できます。

アルゴリズムの手順

• n := flightsの行数
• m := days行列の列数
• (m+1)×nのサイズを持つ2次元配列dpを定義
• i := m-1 として、i >= 0 の間 i を1ずつ減らしながら繰り返し：
  • j := 0 として、j < n の間 j を1ずつ増やしながら繰り返し：
    • k := 0 として、k < n の間 k を1ずつ増やしながら繰り返し：
      • j == k（滞在継続）または flights[j][k] != 0（移動可能）の場合：
        • dp[i][j] := max(dp[i][j], days[j][i] + dp[i+1][k])
• ret := dp[0][0]
• i := 1 として、i < n の間 i を1ずつ増やしながら繰り返し：
  • flights[0][i] != 0 の場合：
    • ret := max(ret, dp[0][i])
• ret を返す

それでは、理解を深めるために以下の実装を見てみましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
      int n = flights.size();
      int m = days[0].size();
      vector<vector<int> > dp(m + 1, vector<int>(n));
      for (int i = m - 1; i >= 0; i--) {
         for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
               if (j == k || flights[j][k]) {
                  dp[i][j] = max(dp[i][j], days[j][i] + dp[i + 1][k]);
               }
            }
         }
      }
      int ret = 0;
      ret = dp[0][0];
      for (int i = 1; i < n; i++) {
         if (flights[0][i]) {
            ret = max(ret, dp[0][i]);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}};
   cout << (ob.maxVacationDays(v1, v2));
}

入力

v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}

出力

12

計算量

• 時間計算量：O(K × N²) — 各週・各都市の組み合わせについて、移動先となりうるすべての都市を試すためです。
• 空間計算量：O(K × N) — DPテーブルの保存に必要なメモリ量です。