部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。

問題へのリンク

問題概要

$N$ 個の正の整数 $a_{0}, \dots, a_{N-1}$ の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。

制約

$1 \le N \le 100$
$1 \le a_{i} \le 100$

考えたこと

この問題とよく似た部分和問題とは次のような問題である。

$N$ 個の正の整数 $a_{0}, \dots, a_{N-1}$ の中からいくつか選んで総和をとった値を $W$ にできるかどうかを判定せよ

この問題に対しては次のような配列 dp を定義することで解くことができる。

${\rm dp}\lbrack i \rbrack \lbrack j \rbrack$ ← $N$ 個の整数のうち最初の $i$ 個の整数の中からいくつか選んだ総和を $j$ にできるかどうか

遷移はこんな感じにできる ( $j$ の範囲に注意)。

dp[i][j] = true のとき
dp[i+1][j] = true;
dp[i+1][j+a[i]] = true;

今回の問題

今回の問題は、具体的な整数 $W$ を作れるかどうかを問うのではなく、作れる整数の個数を求める問題となっている。しかし部分和問題が解けていればほとんど解決済みである。なぜなら、部分和問題を解いて得られた配列 dp を用いることで、次の情報が得られる。

dp[N][j] をみることで、整数 $j$ を作れるかどうかがわかる。

よって、 $j = 1, 2, \dots, 10000$ について dp[N][j] が True であるような $j$ の個数を調べればよい。 $j$ の範囲を 10000 までとしたのは、 $N \le 100$ , $p_{i} \le 100$ という制約から。

計算量は、作りうる最大の整数を $W (\le 10000)$ として、 $O(NW)$ となる。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N; 
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // DP テーブル
    int W = 10000;
    vector<vector<bool>> dp(N+1, vector<bool>(W+1, false));
    dp[0][0] = true;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (!dp[i][j]) continue;
            dp[i+1][j] = true;
            if (j+a[i] <= W) dp[i+1][j+a[i]] = true;
        }
    }

    // 答え
    int res = 0;
    for (int j = 0; j <= W; ++j) {
        if (dp[N][j]) ++res;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

TDPC (Typical DP Contest) A - コンテスト

問題概要

制約

考えたこと

今回の問題

コード