この問題は半分全列挙により解くことができます。

\(M\) 以下の条件は最後に確認すれば十分なため忘れてよいです。また、倉庫を作ったなら荷物を割り当てないのは損なので、区画 \(i\) に倉庫を作るならば荷物量 \(P_i\) を割り当てるとしてよいです。よって問題は「 \(\max_S \sum_{i\in S}P_i\) を求めよ」となります。

\(N\leq 20\) の場合

この場合は \(\mathrm{DP}[S]\) を「\(S\) に含まれない区画には倉庫を作らないときの答え」と定め、 \(S\) に含まれる index が最大の区画 \(f(S)\) に倉庫を建てるかどうか考えることで

\(\mathrm{DP}[S]=\max(\mathrm{DP}[S\setminus\{f(S)\}], \mathrm{DP}[S\setminus(f(S)と直接繋がっている区画の集合)] +P_{f(S)})\)

となります。

集合を適切に整数に対応させることで、集合に対する演算をbit演算により \(O(1)\) で行うことができるとしてよく、この DP テーブルの計算は \(S\) 1 つあたり \(O(1)\)、全体で \(O(2^N)\) でできます。

元の問題

\(N\) 個の区画を、要素数が等しくなるよう 2 つにわけ、\(X,Y\) とします。\(X\) のうち「倉庫を建てる可能性のある区画たち」を全探索することを考えます。このとき、\(X\) 側での荷物量は先程述べた通り \(O(2^\frac{N}{2})\) の前計算により \(O(1)\) で答えることができます。また、\(X\) 側で選んだ区画たちと直接繋がっている区画を除いたものが \(Y\) 側で倉庫を立てる可能性のある区画になります。これも同様に \(O(2^\frac{N}{2})\) の前計算により \(O(1)\) で答えることができます。
「\(X\) 側で選んだ区画たちと直接繋がっている区画を除いたもの」を求めることも、適切な DP と bit 演算により全体で \(O(2^\frac{N}{2})\) でできるとしてよく、全体で \(O(2^\frac{N}{2})\) でこの問題を解くことができました。

この問題のように「前半半分の決め方を全探索し、後半半分の決め方は前半半分の決め方に基づいて高速に求める」という手法を俗に半分全列挙と呼ぶこともあります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  long long m;
  cin >> n >> m >> k;
  vector<long long>p(n);
  for(int i=0; i<n; i++) cin >> p[i];
  vector<long long> G(n);
  for(int i=0; i<k; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u] |= 1LL << v;
    G[v] |= 1LL << u;
  }
  for(int i=0; i<n; i++){
    G[i] |= 1LL << i;
  }

  int n1 = n / 2;
  int n2 = n - n1;

  // 前半
  int mask = (1<<n1) - 1;
  vector<long long>memo(1<<n1);
  for(int s=1; s<(1<<n1); s++){
    int i = 31 - __builtin_clz(s);
    memo[s] = max(memo[s ^ (1<<i)], memo[s & ~G[i] & mask] + p[i]);
  }

  long long ans = *max_element(memo.begin(), memo.end());

  // 後半
  vector<long long>memo2(1<<n2);
  vector<long long>ng(1<<n2);

  for(int s=1; s<(1<<n2); s++){
    int i = 31 - __builtin_clz(s);
    memo2[s] = max(memo2[s ^ (1<<i)], memo2[s & ~(G[i+n1]>>n1)] + p[i+n1]);
    ng[s] = ng[s^(1<<i)] | G[i+n1];
    ans = max(ans, memo2[s] + memo[~ng[s] & mask]);
  }

  cout << min(m, ans) << endl;
}

実装例 (Python)

N, M, K = map(int, input().split())
P = list(map(int, input().split()))
G = [1<<i for i in range(N)]
for _ in range(K):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  G[u] |= 1<<v
  G[v] |= 1<<u

N1 = N // 2
N2 = N - N1

# 前半
mask = (1<<N1) - 1
memo = [0] * (1<<N1)
for s in range(1, 1<<N1):
  i = len(bin(s)) - 3
  memo[s] = max(memo[s ^ (1<<i)], memo[s & ~G[i] & mask] + P[i])

ans = max(memo)
# 後半
memo2 = [0] * (1<<N2)
ng = [0] * (1<<N2)
for s in range(1, 1<<N2):
  i = len(bin(s))-3
  memo2[s] = max(memo2[s ^ (1<<i)], memo2[s & ~(G[i+N1]>>N1)] + P[i+N1])
  ng[s] = ng[s^(1<<i)] | G[i+N1]
  ans = max(ans, memo2[s] + memo[~ng[s] & mask])

print(min(M, ans))