20_bitmask_dp.c

Download
c 263 lines 8.3 KB 
  1/*
  2 * ๋น„ํŠธ๋งˆ์Šคํฌ DP (Bitmask DP)
  3 * TSP, Set Partition, Subset DP
  4 *
  5 * ๋น„ํŠธ ์—ฐ์‚ฐ์„ ํ™œ์šฉํ•œ ์ง‘ํ•ฉ ์ƒํƒœ ํ‘œํ˜„๊ณผ DP์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <limits.h>
 11
 12#define INF INT_MAX
 13#define MIN(a, b) ((a) < (b) ? (a) : (b))
 14#define MAX(a, b) ((a) > (b) ? (a) : (b))
 15
 16/* =============================================================================
 17 * 1. ๋น„ํŠธ ์—ฐ์‚ฐ ๊ธฐ์ดˆ
 18 * ============================================================================= */
 19
 20void print_binary(int n, int bits) {
 21    for (int i = bits - 1; i >= 0; i--) {
 22        printf("%d", (n >> i) & 1);
 23    }
 24}
 25
 26int count_bits(int n) {
 27    int count = 0;
 28    while (n) {
 29        count += n & 1;
 30        n >>= 1;
 31    }
 32    return count;
 33}
 34
 35/* =============================================================================
 36 * 2. TSP (Traveling Salesman Problem)
 37 * ============================================================================= */
 38
 39int tsp(int** dist, int n) {
 40    int full_mask = (1 << n) - 1;
 41    int** dp = malloc((1 << n) * sizeof(int*));
 42    for (int i = 0; i < (1 << n); i++) {
 43        dp[i] = malloc(n * sizeof(int));
 44        for (int j = 0; j < n; j++) dp[i][j] = INF;
 45    }
 46
 47    dp[1][0] = 0;  /* ์‹œ์ž‘์  0 ๋ฐฉ๋ฌธ */
 48
 49    for (int mask = 1; mask <= full_mask; mask++) {
 50        for (int last = 0; last < n; last++) {
 51            if (!(mask & (1 << last))) continue;
 52            if (dp[mask][last] == INF) continue;
 53
 54            for (int next = 0; next < n; next++) {
 55                if (mask & (1 << next)) continue;
 56                if (dist[last][next] == 0) continue;
 57
 58                int new_mask = mask | (1 << next);
 59                int new_cost = dp[mask][last] + dist[last][next];
 60                if (new_cost < dp[new_mask][next]) {
 61                    dp[new_mask][next] = new_cost;
 62                }
 63            }
 64        }
 65    }
 66
 67    int result = INF;
 68    for (int last = 1; last < n; last++) {
 69        if (dp[full_mask][last] != INF && dist[last][0] > 0) {
 70            int cost = dp[full_mask][last] + dist[last][0];
 71            if (cost < result) result = cost;
 72        }
 73    }
 74
 75    for (int i = 0; i < (1 << n); i++) free(dp[i]);
 76    free(dp);
 77    return result;
 78}
 79
 80/* =============================================================================
 81 * 3. ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ
 82 * ============================================================================= */
 83
 84int subset_sum_exists(int arr[], int n, int target) {
 85    int full = 1 << n;
 86    for (int mask = 0; mask < full; mask++) {
 87        int sum = 0;
 88        for (int i = 0; i < n; i++) {
 89            if (mask & (1 << i)) sum += arr[i];
 90        }
 91        if (sum == target) return 1;
 92    }
 93    return 0;
 94}
 95
 96/* =============================================================================
 97 * 4. ์ง‘ํ•ฉ ๋ถ„ํ•  (๋‘ ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ ์ฐจ์ด ์ตœ์†Œ)
 98 * ============================================================================= */
 99
100int min_partition_diff(int arr[], int n) {
101    int total = 0;
102    for (int i = 0; i < n; i++) total += arr[i];
103
104    int full = 1 << n;
105    int min_diff = total;
106
107    for (int mask = 0; mask < full; mask++) {
108        int sum = 0;
109        for (int i = 0; i < n; i++) {
110            if (mask & (1 << i)) sum += arr[i];
111        }
112        int diff = abs(total - 2 * sum);
113        if (diff < min_diff) min_diff = diff;
114    }
115
116    return min_diff;
117}
118
119/* =============================================================================
120 * 5. ํ• ๋‹น ๋ฌธ์ œ (Assignment Problem)
121 * ============================================================================= */
122
123int assignment_problem(int** cost, int n) {
124    int* dp = malloc((1 << n) * sizeof(int));
125    for (int i = 0; i < (1 << n); i++) dp[i] = INF;
126    dp[0] = 0;
127
128    for (int mask = 0; mask < (1 << n); mask++) {
129        if (dp[mask] == INF) continue;
130        int person = count_bits(mask);
131        if (person >= n) continue;
132
133        for (int task = 0; task < n; task++) {
134            if (mask & (1 << task)) continue;
135            int new_mask = mask | (1 << task);
136            int new_cost = dp[mask] + cost[person][task];
137            if (new_cost < dp[new_mask]) dp[new_mask] = new_cost;
138        }
139    }
140
141    int result = dp[(1 << n) - 1];
142    free(dp);
143    return result;
144}
145
146/* =============================================================================
147 * 6. ํ•ด๋ฐ€ํ„ด ๊ฒฝ๋กœ ๊ฐœ์ˆ˜
148 * ============================================================================= */
149
150int hamilton_paths(int** adj, int n, int start) {
151    int** dp = malloc((1 << n) * sizeof(int*));
152    for (int i = 0; i < (1 << n); i++) {
153        dp[i] = calloc(n, sizeof(int));
154    }
155
156    dp[1 << start][start] = 1;
157
158    for (int mask = 0; mask < (1 << n); mask++) {
159        for (int last = 0; last < n; last++) {
160            if (!(mask & (1 << last))) continue;
161            if (dp[mask][last] == 0) continue;
162
163            for (int next = 0; next < n; next++) {
164                if (mask & (1 << next)) continue;
165                if (!adj[last][next]) continue;
166
167                int new_mask = mask | (1 << next);
168                dp[new_mask][next] += dp[mask][last];
169            }
170        }
171    }
172
173    int full = (1 << n) - 1;
174    int total = 0;
175    for (int i = 0; i < n; i++) total += dp[full][i];
176
177    for (int i = 0; i < (1 << n); i++) free(dp[i]);
178    free(dp);
179    return total;
180}
181
182/* =============================================================================
183 * 7. SOS DP (Sum over Subsets)
184 * ============================================================================= */
185
186void sos_dp(int f[], int n) {
187    int full = 1 << n;
188    for (int i = 0; i < n; i++) {
189        for (int mask = 0; mask < full; mask++) {
190            if (mask & (1 << i)) {
191                f[mask] += f[mask ^ (1 << i)];
192            }
193        }
194    }
195}
196
197/* =============================================================================
198 * ํ…Œ์ŠคํŠธ
199 * ============================================================================= */
200
201int main(void) {
202    printf("============================================================\n");
203    printf("๋น„ํŠธ๋งˆ์Šคํฌ DP ์˜ˆ์ œ\n");
204    printf("============================================================\n");
205
206    /* 1. ๋น„ํŠธ ์—ฐ์‚ฐ */
207    printf("\n[1] ๋น„ํŠธ ์—ฐ์‚ฐ ๊ธฐ์ดˆ\n");
208    printf("    5 = "); print_binary(5, 4); printf("\n");
209    printf("    5 | 2 = %d\n", 5 | 2);
210    printf("    5 & 2 = %d\n", 5 & 2);
211    printf("    5 ^ 2 = %d\n", 5 ^ 2);
212    printf("    count_bits(13) = %d\n", count_bits(13));
213
214    /* 2. TSP */
215    printf("\n[2] TSP (์™ธํŒ์› ๋ฌธ์ œ)\n");
216    int** dist = malloc(4 * sizeof(int*));
217    for (int i = 0; i < 4; i++) dist[i] = malloc(4 * sizeof(int));
218    int d[4][4] = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
219    for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) dist[i][j] = d[i][j];
220    printf("    ์ตœ์†Œ ๋น„์šฉ: %d\n", tsp(dist, 4));
221    for (int i = 0; i < 4; i++) free(dist[i]);
222    free(dist);
223
224    /* 3. ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ */
225    printf("\n[3] ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ\n");
226    int arr[] = {3, 34, 4, 12, 5, 2};
227    printf("    ๋ฐฐ์—ด: [3,34,4,12,5,2]\n");
228    printf("    ํ•ฉ 9 ์กด์žฌ: %s\n", subset_sum_exists(arr, 6, 9) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค");
229    printf("    ํ•ฉ 30 ์กด์žฌ: %s\n", subset_sum_exists(arr, 6, 30) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค");
230
231    /* 4. ์ง‘ํ•ฉ ๋ถ„ํ•  */
232    printf("\n[4] ์ง‘ํ•ฉ ๋ถ„ํ•  ์ตœ์†Œ ์ฐจ์ด\n");
233    int arr2[] = {1, 6, 11, 5};
234    printf("    [1,6,11,5]: ์ตœ์†Œ ์ฐจ์ด = %d\n", min_partition_diff(arr2, 4));
235
236    /* 5. ํ• ๋‹น ๋ฌธ์ œ */
237    printf("\n[5] ํ• ๋‹น ๋ฌธ์ œ\n");
238    int** cost = malloc(3 * sizeof(int*));
239    for (int i = 0; i < 3; i++) cost[i] = malloc(3 * sizeof(int));
240    int c[3][3] = {{9, 2, 7}, {6, 4, 3}, {5, 8, 1}};
241    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cost[i][j] = c[i][j];
242    printf("    ๋น„์šฉ ํ–‰๋ ฌ:\n");
243    for (int i = 0; i < 3; i++) {
244        printf("      ");
245        for (int j = 0; j < 3; j++) printf("%d ", c[i][j]);
246        printf("\n");
247    }
248    printf("    ์ตœ์†Œ ๋น„์šฉ: %d\n", assignment_problem(cost, 3));
249    for (int i = 0; i < 3; i++) free(cost[i]);
250    free(cost);
251
252    /* 6. ๋ณต์žก๋„ */
253    printf("\n[6] ๋น„ํŠธ๋งˆ์Šคํฌ DP ๋ณต์žก๋„\n");
254    printf("    TSP: O(nยฒ ร— 2^n)\n");
255    printf("    ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ: O(n ร— 2^n)\n");
256    printf("    ํ• ๋‹น ๋ฌธ์ œ: O(n ร— 2^n)\n");
257    printf("    SOS DP: O(n ร— 2^n)\n");
258
259    printf("\n============================================================\n");
260
261    return 0;
262}