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