D - Cooking

・問題URL

https://atcoder.jp/contests/abc204/tasks/abc204_d

・発想

・Tの各要素を２つのうちどちらかのオーブンに割り振って、できるだけ均等になるようにする。んで大きいほうが答え(すなわちΣT-(Tから合計が(ΣT)/2を超えないように選んだ時の最大値))ってのはすぐに分かり、これはナップサックDPとかいうやつだなと思ったが知らんので調べる。
・本番では苦し紛れに「Tを降順にsortして、合計が少ない方に入れていく」という解法を思いついたがこれは嘘。(解説によると例えば、T=4,3,3,2,2の時、この方法だとA=8,B=6になるが、実際はA=B=7で二等分できる。たしかに。)

・解法

ナップサックDP(制約上簡単な方でおけ。)で重さと価値を両方T[i]にしたやつ(重さと価値をわざわざ同じにするならもっと簡単な方法ある気がする)。

・コード

int main(){
  
 int N;
 cin>>N;
 vector<ll>T(N);
 ll sum=0;
 rep(i,N){
   cin>>T[i];
   sum+=T[i];
 }
 int dp[110][110000];
 for(int j=0;j<=sum/2;j++){
   if(T[0]<=j)dp[0][j]=T[0];
 }
 for(int i=1;i<N;i++){
   for(int j=0;j<=sum/2;j++){
     if(j-T[i]>=0)dp[i][j]=MAX(dp[i-1][j],dp[i-1][j-T[i]]+T[i]);
     else dp[i][j]=dp[i-1][j];
   }
 }

 cout<<sum-dp[N-1][sum/2]<<endl;

}