C++で解くIPO問題：最大k件のプロジェクト選択で資本を最大化する方法

問題の概要

ある会社AがまもなくIPO（新規株式公開）を控えているとしましょう。自社の株式を良い価格で売却するために、A社はIPO前にいくつかのプロジェクトへ取り組み、資本を増やしたいと考えています。しかし、A社のリソースには限りがあり、IPOまでに完了できるのは最大k件の異なるプロジェクトだけです。最大k件のプロジェクトを完了した後の総資本を最大化する最適な戦略を設計して、A社を助けましょう。

各プロジェクトiには純利益 Pi と、着手に必要な最小資本 Ci が設定されています。初期資本は W です。プロジェクトを完了すると純利益を獲得でき、その利益は総資本に加算されます。

つまりこの問題は、与えられたプロジェクトの中から最大k件の異なるプロジェクトを選び、最終的な資本を最大化することです。答えとして、最大化された最終資本を出力します。

具体例

入力が以下の場合を考えてみます。

• k = 2（実行できるプロジェクト数）
• W = 0（初期資本）
• Profits = [1, 2, 4]（各プロジェクトの純利益）
• Capital = [0, 1, 1]（各プロジェクトの必要資本）

このとき出力は 5 になります。手順を見てみましょう。

1. 初期資本が0のため、着手できるのはインデックス0のプロジェクトのみ。これを実行して利益1を得て、資本は1になります。
2. 資本1があれば、インデックス1または2のプロジェクトに着手できます。より多くの利益を得るため、利益4のインデックス2を選択します。

したがって最終的な答えは 0 + 1 + 4 = 5 となります。

解法のアプローチ

この問題は、貪欲法と優先度付きキュー（ヒープ）を組み合わせることで効率的に解けます。考え方はシンプルで、「現在の資本で着手可能なプロジェクトの中から、純利益が最大のものを選ぶ」という操作をk回繰り返すだけです。

具体的な手順は以下の通りです。

• 優先度付きキュー pqCapital と pqMain を作成する
• n := Profits のサイズとする
• i := 0 から初期化し、i < n の間、i を1ずつ増やしながら実行する
  • { Profits[i], Capital[i] } を pqCapital に挿入する
• i := 0 から初期化し、i < k の間、i を1ずつ増やしながら実行する
  • pqCapital が空でなく、先頭要素の資本値が W 以下である間、次を繰り返す
    • pqCapital の先頭要素を pqMain に移動する
    • pqCapital からその要素を削除する
  • pqMain が空の場合はループを抜ける（これ以上着手できるプロジェクトがない）
  • W := W + pqMain の先頭要素の利益値とする
  • pqMain から先頭要素を削除する
• W を返す

ここで重要なポイントは、pqCapital を「必要資本の昇順」に、pqMain を「純利益の降順」に並べることです。こうすることで、現在の資本 W で着手できるすべてのプロジェクトを pqMain へ移しておき、その中から最も利益の大きいものを即座に取り出せるようになります。

C++での実装例

それでは、上記のアルゴリズムをC++で実装してみましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Comparator{
   bool operator() (pair <int, int> a, pair <int, int> b){
      return !(a.second < b.second);
   }
};
class Solution {
public:
   int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
   priority_queue < pair <int, int>, vector < pair <int, int> >, Comparator> pqCapital;
   priority_queue < pair <int ,int> > pqMain;
   int n = Profits.size();
   for(int i = 0; i < n; i++){
      pqCapital.push({Profits[i], Capital[i]});
   }
   for(int i = 0; i < k; i++){
      while(!pqCapital.empty() && pqCapital.top().second <= W){
         pqMain.push(pqCapital.top());
         pqCapital.pop();
      }
      if(pqMain.empty()) break;
         W += pqMain.top().first;
         pqMain.pop();
      }
      return W;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,4}, v1 = {0,1,1};
   cout << (ob.findMaximizedCapital(2,0, v, v1));
}

入力

2
0
[1,2,4]
[0,1,1]

出力

5

計算量について

時間計算量は O(n log n) オーダーで評価できます。すべてのプロジェクトを pqCapital へ挿入するのに O(n log n) かかり、着手可能なプロジェクトを pqMain へ移す処理では各プロジェクトが高々1回しか移動しないためです。さらに、k回の選択それぞれに対して O(log n) のコストが発生します。空間計算量は、すべてのプロジェクトを保持するために O(n) となります。