Algoogle

Algorithm for Programming Contest

AOJ 2333 My friends are small

Category: AOJ Tag: dp

My friends are small

問題概要


N人の友達がいて, 重さの総和がWまで一緒に運べる(運べる余裕があるのに置いて行ったりはしない).
このとき運ぶ友達の組み合わせの総数を求めよ.

解法


重さの小さい順にソートしておいて, 「i番目まで全て運んで, かつi+1番目を運ばない」場合をすべて考える.
このときi+2番目以降を重さW-sum[i]の範囲で自由にえらぶナップサックを考えてDPすればよい.
それぞれの場合でw[i+1]以上の余裕ができない場合の数を足し合わせれば答えになる.

コード


(2333.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int mod = 1e9+7;
int N, W, w[256];
int dp[10010], sum[256];
inline void f(int &a, int b){ a=(a+b)%mod;}

int solve(){
    sort(w,w+N);
    rep(i,N) sum[i+1] = sum[i] + w[i];
    int ans = sum[N]==W;
    rep(i,N){
        memset(dp, 0, sizeof(dp));
        if(sum[i] > W) break;
        dp[sum[i]] += 1;
        repi(j,i+1,N) for(int k = W; k-w[j]>=sum[i]; k--)
            f(dp[k], dp[k-w[j]]);
        repi(j,W-w[i]+1,W+1) f(ans, dp[j]);
    }
    return ans;
}


int main(){
    cin >> N >> W;
    rep(i,N) cin >> w[i];
    cout << solve() << endl;
    return 0;
}

Comments