Combinatorial - 0-1 Knapsack Problem

ナップザック問題 | 動的計画法 | Aizu Online Judge

シンプルなナップザック問題。

int main() {
    int N, W; cin >> N >> W;
    int v[105], w[105];
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
    int dp[105][10005];
    memset(dp, -1, sizeof(dp));
    int res = 0;
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            int k = j - w[i];
            if (k >= 0 && dp[i][k] >= 0) {
                dp[i + 1][j] = max(dp[i][j], dp[i][k] + v[i]);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
            res = max(res, dp[i + 1][j]);
        }
    }

    printf("%d\n", res);
    return 0;
}