C++の練習を兼ねて, 第１１回 アルゴリズム実技検定 過去問 の 問題H (2つのナップサック) を解いてみた.
■感想.
1. 問題Hは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 個人的には, 問題Hで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト 第１１回 アルゴリズム実技検定 の 各リンク を ご覧下さい.
■C++版プログラム(問題H／AC版).
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const LL INF = 202020202020202020; int w[101], v[101]; LL dp[2][303][303]; int main(){ // 1. 入力情報. int N, A, B; scanf("%d %d %d", &N, &A, &B); rep(i, N) scanf("%d %d", &w[i + 1], &v[i + 1]); // 2. 初期化. rep(i, 2) rep(j, 303) rep(k, 303) dp[i][j][k] = -INF; dp[0][0][0] = 0; // 3. dp更新. repx(i, 1, N + 1){ // 今回分(初期化). rep(j, 303) rep(k, 303) dp[1][j][k] = dp[0][j][k]; // 今回分更新. repr(j, A, 0){ repr(k, B, 0){ if(dp[0][j][k] >= 0){ // 一つ目のナップサック. if(w[i] + j <= A){ dp[1][w[i] + j][k] = max(dp[1][w[i] + j][k], dp[0][j][k] + (LL)v[i]); } // 二つ目のナップサック. if(w[i] + k <= B){ dp[1][j][w[i] + k] = max(dp[1][j][w[i] + k], dp[0][j][k] + (LL)v[i]); } } } } // 前回分(保存). rep(j, 303) rep(k, 303) dp[0][j][k] = dp[1][j][k]; } // 4. お菓子の美味しさの合計としてありうる最大値は？ LL ans = 0; rep(j, A + 1) rep(k, B + 1) ans = max(ans, dp[1][j][k]); // 5. 出力. printf("%lld\n", ans); return 0; } |
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
[入力例] 6 8 9 2 6 4 1 5 9 3 1 5 3 5 8 [出力例] 24 ※AtCoderテストケースより [入力例] 20 70 60 7 94 18 33 14 26 10 1 9 57 2 80 19 74 16 10 15 18 10 38 13 90 12 23 3 3 8 11 18 10 3 42 3 66 3 90 10 2 5 45 [出力例] 772 ※AtCoderテストケースより [入力例] 7 8 10 3 7 8 1 9 15 10 15 2 7 7 1 3 15 [出力例] 44 [入力例] 15 20 22 7 7 9 1 8 15 1 15 7 50 9 37 6 23 8 21 2 11 5 19 8 11 2 13 10 20 8 32 1 22 [出力例] 222 [入力例] 30 256 234 76 53 70 169 77 330 42 23 42 263 14 155 38 198 58 203 13 50 43 153 10 103 13 103 80 110 59 277 67 150 21 59 27 123 22 131 56 203 58 260 16 211 12 199 33 274 45 268 44 287 1 80 11 9 64 185 13 248 73 76 [出力例] 3333 [入力例] 50 300 300 15 20022 38 18592 4 5470 1 2926 19 2156 13 2548 42 30859 34 31505 50 1414 38 32713 9 16687 15 23146 19 24343 6 19052 9 30208 10 33332 7 2013 27 28004 8 13704 10 2819 48 10548 43 20648 19 11678 47 23502 6 25309 31 29272 35 30446 2 2392 19 28872 47 3897 29 30287 24 667 37 2891 34 21064 25 15530 5 11073 5 22751 2 8789 27 2078 46 18138 43 16273 25 3429 13 16627 15 31875 34 31875 6 29727 4 37547 6 633 21 23994 10 33196 [出力例] 777777 |
■参照サイト
第１１回 アルゴリズム実技検定 過去問