採択するかどうかの \(2\) 択を \(N\) 個行う全てのパターンを調べ尽くしたい時、 bit全探索 が有効です。

• 採択する集合を \(2^N\) 通り全て試す。その中で、 以下の \(2\) つの制約を判定すればよい。
  • 予算が \(K\) 以下に収まるかどうか
    • bit が立っているプロジェクトについて、費用を足し合わせればよいです。
  • \(M\) 個の「同時には採択できない」制約を満たすかどうか
    • 当該プロジェクトの bit が双方立っているかどうかで判定できます。
• あとは、合法な選び方全てについての利益の総和の最大値を取ればよいです。

各パターンについて時間計算量 \(O(N+M)\) かけても全体で時間計算量 \(O(2^N(N+M))\) となり、実行時間制限に間に合います。

Bonus: これよりも高速な解法が存在します。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> C(N),P(N);
  for(ll i=0;i<N;i++){
    cin >> C[i] >> P[i];
  }
  vector<ll> U(M),V(M);
  for(ll i=0;i<M;i++){
    cin >> U[i] >> V[i];
    U[i]--; V[i]--;
  }

  ll res=0;
  for(ll i=0;i<(1ll<<N);i++){
    ll cost=0;
    ll prof=0;
    for(ll j=0;j<N;j++){
      if(i&(1ll<<j)){
        cost+=C[j];
        prof+=P[j];
      }
    }
    if(cost>K){continue;}
    
    bool ok=true;
    for(ll j=0;j<M;j++){
      if((i&(1ll<<U[j]))>0 && (i&(1ll<<V[j]))>0){
        ok=false;
        break;
      }
    }
    if(ok){
      res=max(res,prof);
    }
  }
  cout << res << "\n";
  return 0;
}