Combinatorial - Knapsack Problem

Knapsack Problem | Aizu Online Judge

Combinatorial - 0-1 Knapsack Problem - アルゴリズムのメモ帳 とほぼ同じ問題。

続けて解いたので、ちょっとずるして上で解いたものを再利用した。

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]);
            }

            if (k >= 0 && dp[i + 1][k] >= 0) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][k] + v[i]);
            }

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            res = max(res, dp[i + 1][j]);
        }
    }

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