この問題は DP により解くことができます。

\(S=\sum A_i\) とします。「 \(N\) 人から何人かを選んで、力の和を \(x\) にできるか？」を全ての \(0\leq x \leq S/2\) について求めることができれば、元の問題に答えることができます。

この問題は部分和問題なので、\(\mathrm{DP}[i][s]\) を「 \(i\) 番目の選手までから何人かを選んで、力の和を \(s\) にできるか？」と定めるDPにより解くことができます。しかし、このDPは \(O(NS)\) となるため、実行時間制限に間に合わせることは困難です。そこで、俗にbitset高速化と呼ばれる手法を用います。

\(\mathrm{DP'}[i]\) を、 \(s\) bit 目が \(\mathrm{DP}[i][s]\) となるような \(S\) bit の bit 列と定めます。

このとき、DP の遷移は \(\mathrm{DP'}[i+1]=\mathrm{DP'}[i] \mathbin{|} (\mathrm{DP'}[i] \ll A_{i+1})\) となります（\(|\) は bitwise or、 \(\ll\) はビットシフト）。これにより ワードサイズを \(w\) として、この遷移は \(O(S/w)\) で行うことができ、全体で \(O(NS/w)\) で答えを求めることができます。

このような操作を可能とする bit 列の表現はプログラミング言語ごとに異なります。C++では bitset と呼ばれるデータ構造を用います。Pythonでは単に int を用いることができます。

実装例 (C++)

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

int main(){
  int n;
  cin >> n;
  bitset<100010> dp;
  dp[0]=true;
  int s = 0;
  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    s += a;
    dp |= dp << a;
  }

  for(int i=s/2; i>=0; i--){
    if(dp[i]){
      cout << i << endl;
      return 0;
    }
  }
}

実装例 (Python)

N = int(input())
dp = 1
S = 0
for _ in range(N):
  a = int(input())
  S += a
  dp |= dp << a

for i in range(S//2, -1, -1):
  if dp & (1<<i):
    print(i)
    exit()