Tham lam

#include <stdio.h>

/* Đổi số tiền thành ít tờ nhất. Tham lam: luôn lấy mệnh giá lớn nhất còn dùng được. */
int doi_tien_tham_lam(const long *mg, size_t n, long tien, long *so_to)
{
    int tong_to = 0;

    for (size_t i = 0; i < n; ++i) {
        so_to[i] = tien / mg[i];
        tien    %= mg[i];
        tong_to += (int)so_to[i];
    }

    return (tien == 0) ? tong_to : -1;      /* -1 nếu không đổi hết được */
}

int main(void)
{
    /* Hệ mệnh giá Việt Nam, sắp giảm dần */
    long mg[] = { 500000, 200000, 100000, 50000, 20000, 10000, 5000, 2000, 1000 };
    size_t n  = sizeof mg / sizeof mg[0];
    long   so_to[16];

    long tien = 878000;
    int  tong = doi_tien_tham_lam(mg, n, tien, so_to);

    printf("doi %ld dong bang %d to:\n", tien, tong);

    for (size_t i = 0; i < n; ++i)
        if (so_to[i] > 0) printf("  %ld to %ld\n", so_to[i], mg[i]);

    return 0;
}

#include <limits.h>
#include <stdlib.h>

/* Số tờ ít nhất để đổi đúng số tiền. Trả về -1 nếu không đổi được.
   O(n nhân tien) thời gian, O(tien) bộ nhớ. Bài 28.3 nói kỹ. */
int doi_tien_dp(const long *mg, size_t n, long tien)
{
    if (tien < 0) return -1;

    int *dp = malloc((size_t)(tien + 1) * sizeof *dp);

    if (dp == NULL) return -1;

    dp[0] = 0;

    for (long t = 1; t <= tien; ++t) {
        dp[t] = INT_MAX;

        for (size_t i = 0; i < n; ++i)
            if (mg[i] <= t && dp[t - mg[i]] != INT_MAX &&
                dp[t - mg[i]] + 1 < dp[t])
                dp[t] = dp[t - mg[i]] + 1;
    }

    int kq = (dp[tien] == INT_MAX) ? -1 : dp[tien];

    free(dp);

    return kq;
}

#include <stdlib.h>

typedef struct { int bat_dau, ket_thuc; } HD;

static int theo_ket_thuc(const void *pa, const void *pb)
{
    const HD *a = pa, *b = pb;

    if (a->ket_thuc != b->ket_thuc)
        return (a->ket_thuc > b->ket_thuc) - (a->ket_thuc < b->ket_thuc);

    return (a->bat_dau > b->bat_dau) - (a->bat_dau < b->bat_dau);
}

/* Chọn nhiều nhất bao nhiêu hoạt động không chồng lấn.
   Ghi chỉ số các hoạt động được chọn vào ra nếu ra khác NULL. */
int chon_hoat_dong(HD *a, size_t n, size_t *ra)
{
    if (n == 0) return 0;

    qsort(a, n, sizeof *a, theo_ket_thuc);      /* sắp theo THỜI ĐIỂM KẾT THÚC */

    int    dem  = 1;
    int    cuoi = a[0].ket_thuc;

    if (ra != NULL) ra[0] = 0;

    for (size_t i = 1; i < n; ++i)
        if (a[i].bat_dau >= cuoi) {
            if (ra != NULL) ra[dem] = i;

            ++dem;
            cuoi = a[i].ket_thuc;
        }

    return dem;
}

#include <stdlib.h>
#include <string.h>

typedef struct HNode {
    unsigned long   tan_suat;
    int             ky_tu;        /* -1 nếu là nút trong */
    struct HNode   *trai, *phai;
} HNode;

/* Heap nhỏ nhất theo tần suất, cùng mẫu Bài 23.4. */
typedef struct { HNode **d; size_t n, cap; } Heap;

static int nho_hon(const HNode *a, const HNode *b)
{
    return a->tan_suat < b->tan_suat;
}

/* Dựng cây Huffman. Trả về gốc, hoặc NULL nếu hết bộ nhớ. */
HNode *huffman(const unsigned long *tan_suat, int so_ky_tu)
{
    Heap h;

    heap_khoi_tao(&h);

    /* Đưa mọi ký tự có tần suất khác 0 vào heap */
    for (int c = 0; c < so_ky_tu; ++c)
        if (tan_suat[c] > 0) {
            HNode *n = malloc(sizeof *n);

            if (n == NULL) { heap_huy_sau(&h); return NULL; }

            n->tan_suat = tan_suat[c];
            n->ky_tu    = c;
            n->trai     = NULL;
            n->phai     = NULL;

            if (heap_push(&h, n) != 0) { free(n); heap_huy_sau(&h); return NULL; }
        }

    if (h.n == 0) return NULL;

    /* Gộp hai nút nhỏ nhất, lặp tới khi còn một nút */
    while (h.n > 1) {
        HNode *a, *b;

        heap_pop(&h, &a);
        heap_pop(&h, &b);

        HNode *cha = malloc(sizeof *cha);

        if (cha == NULL) { free(a); free(b); heap_huy_sau(&h); return NULL; }

        cha->tan_suat = a->tan_suat + b->tan_suat;
        cha->ky_tu    = -1;
        cha->trai     = a;
        cha->phai     = b;

        if (heap_push(&h, cha) != 0) { /* dọn dẹp */ return NULL; }
    }

    HNode *goc;

    heap_pop(&h, &goc);
    heap_huy(&h);

    return goc;
}

/* Vi du: chuoi "abracadabra", tan suat

     a: 5   b: 2   r: 2   c: 1   d: 1

   Buoc 1: gop c(1) va d(1)  ->  nut X(2)
     Heap: b(2) r(2) X(2) a(5)

   Buoc 2: gop b(2) va r(2)  ->  nut Y(4)
     Heap: X(2) Y(4) a(5)

   Buoc 3: gop X(2) va Y(4)  ->  nut Z(6)
     Heap: a(5) Z(6)

   Buoc 4: gop a(5) va Z(6)  ->  goc(11)

   Cay:
                (11)
               /    \
            a(5)     Z(6)
                    /    \
                 X(2)     Y(4)
                /   \    /   \
              c(1) d(1) b(2) r(2)

   Ma:  a = 0      (1 bit)
        c = 100    (3 bit)
        d = 101    (3 bit)
        b = 110    (3 bit)
        r = 111    (3 bit)

   Do dai: 5*1 + 1*3 + 1*3 + 2*3 + 2*3 = 5 + 3 + 3 + 6 + 6 = 23 bit
   So voi ASCII 8 bit: 11 * 8 = 88 bit
   Ti le nen: 23/88 = 26 phan tram                              */

/* Sinh hàng nghìn dữ liệu nhỏ ngẫu nhiên, so tham lam với vét cạn.
   Không chứng minh được tính đúng, nhưng bắt được phản ví dụ rất nhanh. */
int kiem_tham_lam(int so_lan, int n_toi_da)
{
    srand(2024);

    for (int lan = 0; lan < so_lan; ++lan) {
        int n = 1 + rand() % n_toi_da;

        /* Sinh dữ liệu nhỏ ngẫu nhiên */
        int a[16];

        for (int i = 0; i < n; ++i) a[i] = 1 + rand() % 20;

        int tl = giai_tham_lam(a, n);
        int vc = giai_vet_can(a, n);      /* O(2^n), chỉ dùng với n nhỏ */

        if (tl != vc) {
            printf("PHAN VI DU voi n = %d: ", n);

            for (int i = 0; i < n; ++i) printf("%d ", a[i]);

            printf("\n  tham lam = %d, toi uu = %d\n", tl, vc);

            return 0;
        }
    }

    printf("qua %d phep thu, khong tim thay phan vi du\n", so_lan);

    return 1;
}