読者です 読者をやめる 読者になる 読者になる

AOJ2333 My friends are small

問題
重さのみのナップザック問題が与えられる。
任意の順番で品物を詰めることができるが、まだ品物が入る場合は出来る限り詰めなければならない。
N個の品物を容量Wのナップザックに入れる組み合わせの数を答えよ。

解説
ナップザック問題の変形問題の典型。
出来る限り詰める必要があることをどう処理するかが問題の肝である。
品物の重さを降順ソートしておけば、「品物iで詰めなかったら、後全部詰めても品物iの容量以上余ってしまう」という判定ができる。
昇順ソートして処理しようとすると、「k番目の品物を初めて入れなかったが、全部の品物を試してみた後、k番目の品物以上の容量が余ってしまった。」という判定になる。
これだと、どの品物を初めて袋に入れなかったかを記憶しておく必要があり、計算量がN倍担って非効率の上実装も面倒となる。

類題には次のような問題がある。
http://arc042.contest.atcoder.jp/tasks/arc042_c

int main() {
 
  int N, W; cin >> N >> W;
  vector<int> ws(N);
  vector<int> wsum(N);
  rep(i, N) {
    cin >> ws[i];
  }
 
  sort(all(ws), greater<int>());
 
  rep(i, N) {
    wsum[i] = ws[i] + (i ? wsum[i-1] : 0);
  }
 
  static int dp[2][10001];
  dp[0][W] = 1;
 
  rep(i, N) {
    fill(dp[(i+1)&1], dp[(i+1)&1] + W + 1, 0);
    rep(j, W+1) {
      if(wsum[N-1] - (i ? wsum[i-1] : 0) <= j) {
        dp[(i+1)&1][j] = 0;
      } else {
        dp[(i+1)&1][j] = dp[i&1][j];
      }
 
      if(ws[i] <= j) {
        dp[(i+1)&1][j-ws[i]] += dp[i&1][j];
        dp[(i+1)&1][j-ws[i]] %= MOD;
      }
    }
  }
   
  int ans = 0;
 
  rep(i, W+1) {
    ans += dp[N&1][i];
    ans %= MOD;
  }
 
  cout << ans << endl;
 
  return 0;
}