yukicoder No.4 重りと天秤 解説

問題文

前提知識

dp

解説

いわゆる部分和問題というタイプのやつ。
まず制約が $N\leqq 100$ なのでbit全探索および再帰関数では厳しそう。
しかし、代わりに $W\leqq 100$ という制約もあるので、dp(動的計画法)で解けると考えられる。

dpのかたち

dpのかたち

$dp[i][j]=W_1$~$W_i$ まででjを作ることができるかどうか。 dpの横のサイズは $10001$ もあれば十分。(あり得る解は $0$ ~ $10000$ のため)

遷移方法

遷移方法

$dp[i][j]$ がtrueなら $dp[i+1][j]$ もtrue。 $dp[i][j]$ がtrueなら $dp[i+1][j+w[i]]$ もtrue。

結果

遷移方法

$(\sum_{i=1}^{N}W_i)\bmod{2}=1$ ならimpossible(事故を防ぐために事前に場合分けしておく)

そうでないなら
$dp[n][sum/2]$ がtrueならpossible
そうでないならimpossible

計算量は $O(N\ max(W)^2)$

C++での解答例

C++23での解答例

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

int main(){
  int n,sum=0;cin>>n;
  vector<int> w(n);
  for(int i=0;i<n;i++){
    cin>>w[i];
    sum+=w[i];
  }
  if(sum%2==1){
    cout<<"impossible\n";
    return 0;
  }
  vector<vector<bool>> dp(n+1,vector<bool>(10099,false));
  dp[0][0]=true;
  for(int i=0;i<n;i++){
    for(int j=0;j<=10000;j++){
      if(!dp[i][j])continue;
      dp[i+1][j]=true;
      dp[i+1][j+w[i]]=true;
    }
  }
  cout<<(dp[n][sum/2] ? "possible\n":"impossible\n");
}