实验内容

（1）编写程序实现0-1背包问题的递归，备忘录，及动态规划的比较。

（2）画出运行时间与n*C的曲线，并分析原因.

递归代码：

// 递归算法
int Recursive(int C, int weights[], int values[], int n) {
    if (n == 0 || C == 0) {
        return 0;
    }
    if (weights[n - 1] > C) {
        return Recursive(C, weights, values, n - 1);
    }
    else {
        return max(Recursive(C, weights, values, n - 1),
            values[n - 1] + Recursive(C - weights[n - 1], weights, values, n - 1));
    }
}

备忘录代码：

// 备忘录算法
int Memoization(int C, int weights[], int values[], int n, int** memo) {
    if (n == 0 || C == 0) {
        return 0;
    }
    if (memo[n][C] != -1) {
        return memo[n][C];
    }
    if (weights[n - 1] > C) {
        memo[n][C] = Memoization(C, weights, values, n - 1, memo);
    }
    else {
        memo[n][C] = max(Memoization(C, weights, values, n - 1, memo),
            values[n - 1] + Memoization(C - weights[n - 1], weights, values, n - 1, memo));
    }
    return memo[n][C];
}

  动态规划代码：

// 动态规划算法
int Dynamic(int C, int weights[], int values[], int n) {
   int** V = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        V[i] = (int*)malloc((C + 1) * sizeof(int));
    }

    // 初始化边界条件
    for (int i = 0; i <= n; i++) {
        V[i][0] = 0;
    }
    for (int j = 0; j <= C; j++) {
        V[0][j] = 0;
    }

    // 动态规划计算最大价值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (weights[i - 1] > j) {
                V[i][j] = V[i - 1][j];
            } else {
                V[i][j] = max(V[i - 1][j], values[i - 1] + V[i - 1][j - weights[i - 1]]);
            }
        }
    }

    int max_value = V[n][C];

    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(V[i]);
    }
    free(V);

    return max_value;
}

递归、备忘录、动态规划结果（部分）：

递归、备忘录、动态规划运行时间与n*C的对比:

实验结果：由运行结果可视化分析可以得出，当n逐渐增大后，直接插入排序所花费的时间明显高于合并排序的时间。

原因分析：

1)递归:

时间复杂度为 O(2^n),递归算法是最简单的实现方式，但在处理大规模问题时可能会导致指数级的计算复杂度。因为在每个节点，递归算法会调用自身两次，分别处理放入当前物品和不放入当前物品的情况。这种重复计算会导致算法的效率较低，尤其是当问题规模较大时。因此，随着n和C的增加，递归算法的运行时间呈指数级增长。

2)备忘录：

时间复杂度为 O(nC),通过利用备忘录的记忆功能，避免了重复计算，显著提高了算法的效率。因此，备忘录算法的运行时间相较于递归算法有所减少，并且随着n和C的增加，运行时间的增长速度较为缓慢。

3)动态规划：

时间复杂度为 O(nC),按照自底向上的方式计算子问题的解，并逐步构建出整个问题的解。相对于递归和备忘录算法，动态规划算法具有更高的效率和更小的时间复杂度。随着n和C的增加，动态规划算法的运行时间增长速度较为稳定，呈线性或近似线性的关系。

源码：

//最长公共子序列递归备忘录，动态规划算法比较
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

// 递归备忘录方法求解最长公共子序列长度
int memoizationLCS(char* x, char* y, int i, int j, int** memo) {
    if (i == 0 || j == 0) {
        return 0;
    }
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    if (x[i - 1] == y[j - 1]) {
        memo[i][j] = memoizationLCS(x, y, i - 1, j - 1, memo) + 1;
    }
    else {
        memo[i][j] = max(memoizationLCS(x, y, i, j - 1, memo), memoizationLCS(x, y, i - 1, j, memo));
    }
    return memo[i][j];
}

// 动态规划方法求解最长公共子序列长度
int dynamicLCS(char* x, char* y, int m, int n) {
    int** L = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        L[i] = (int*)malloc((n + 1) * sizeof(int));
    }

    // 初始化L数组
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            }
            else if (x[i - 1] == y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            }
            else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    int lcsLength = L[m][n];

    // 释放L数组的内存
    for (int i = 0; i <= m; i++) {
        free(L[i]);
    }
    free(L);

    return lcsLength;
}

// 生成随机字符串
void RandomString(char* str, int length) {
    const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int charsetSize = sizeof(charset) - 1;

    srand(time(NULL));

    for (int i = 0; i < length; i++) {
        int index = rand() % charsetSize;
        str[i] = charset[index];
    }

    str[length] = '';
}

int main(int argc, char* argv[]) {
    int n = 1220;
    char* x = (char*)malloc((n + 1) * sizeof(char));
    RandomString(x, n);
    int m = 1550;
    char* y = (char*)malloc((m + 1) * sizeof(char));
    RandomString(y, m);

    // 使用递归备忘录方法求解最长公共子序列长度
    int** memo = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        memo[i] = (int*)malloc((m + 1) * sizeof(int));
        memset(memo[i], -1, (m + 1) * sizeof(int));
    }
    clock_t start = clock();
    int lcsLengthMemoization = memoizationLCS(x, y, n, m, memo);
    clock_t end = clock();
    printf("递归备忘录方法求解最长公共子序列长度: %d
", lcsLengthMemoization);
    printf("递归备忘录方法运行时间: %f seconds
", (double)(end - start) / CLOCKS_PER_SEC);

    // 释放memo数组的内存
    for (int i = 0; i <= n; i++) {
        free(memo[i]);
    }
    free(memo);

    // 使用动态规划方法求解最长公共子序列长度
    start = clock();
    int lcsLengthDynamic = dynamicLCS(x, y, n, m);
    end = clock();
    printf("动态规划方法求解最长公共子序列长度: %d
", lcsLengthDynamic);
    printf("动态规划方法运行时间: %f seconds
", (double)(end - start) / CLOCKS_PER_SEC);

    // 释放输入串x和y的内存
    free(x);
    free(y);

    // 输出n和m的乘积与程序运行时间之间的关系
    double timeMemoization = (double)(end - start) / CLOCKS_PER_SEC;
    start = clock();
    for (int i = 0; i < n * m; i++) {
        // do nothing
    }
    end = clock();
    double timeDummy = (double)(end - start) / CLOCKS_PER_SEC;
    printf("程序运行时间: %f seconds
",timeMemoization - timeDummy);

    printf("
");
    return 0;
}



#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

// 递归算法
int Recursive(int C, int weights[], int values[], int n) {
    if (n == 0 || C == 0) {
        return 0;
    }
    if (weights[n - 1] > C) {
        return Recursive(C, weights, values, n - 1);
    }
    else {
        return max(Recursive(C, weights, values, n - 1),
            values[n - 1] + Recursive(C - weights[n - 1], weights, values, n - 1));
    }
}

// 备忘录算法
int Memoization(int C, int weights[], int values[], int n, int** memo) {
    if (n == 0 || C == 0) {
        return 0;
    }
    if (memo[n][C] != -1) {
        return memo[n][C];
    }
    if (weights[n - 1] > C) {
        memo[n][C] = Memoization(C, weights, values, n - 1, memo);
    }
    else {
        memo[n][C] = max(Memoization(C, weights, values, n - 1, memo),
            values[n - 1] + Memoization(C - weights[n - 1], weights, values, n - 1, memo));
    }
    return memo[n][C];
}

// 动态规划算法
int Dynamic(int C, int weights[], int values[], int n) {
   int** V = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        V[i] = (int*)malloc((C + 1) * sizeof(int));
    }

    // 初始化边界条件
    for (int i = 0; i <= n; i++) {
        V[i][0] = 0;
    }
    for (int j = 0; j <= C; j++) {
        V[0][j] = 0;
    }

    // 动态规划计算最大价值
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (weights[i - 1] > j) {
                V[i][j] = V[i - 1][j];
            } else {
                V[i][j] = max(V[i - 1][j], values[i - 1] + V[i - 1][j - weights[i - 1]]);
            }
        }
    }

    int max_value = V[n][C];

    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(V[i]);
    }
    free(V);

    return max_value;
}


int main() {
    int n = 20; // 物品数量
    int C = 50; // 背包容量

    int weights[20];
    int values[20];
    srand(time(0));
    for (int i = 0; i < n; i++) {
        weights[i] = rand() % 10 + 1; // 随机生成物品的重量
        values[i] = rand() % 10 + 1;  // 随机生成物品的价值
    }

    printf("n	C	Recursive	Memoization	Dynamic
");

    for (int i = 1; i <= n; i++) {
        int** memo = (int**)malloc((i + 1) * sizeof(int*));
        for (int j = 0; j <= i; j++) {
            memo[j] = (int*)malloc((C + 1) * sizeof(int));
            for (int k = 0; k <= C; k++) {
                memo[j][k] = -1;
            }
        }

        clock_t start, end;
         clock_t start, end;
        double cpu_time_used1 = 0;
        double cpu_time_used2 = 0;
        double cpu_time_used3 = 0;

        start = clock();
        Recursive(C, weights, values, i);
        end = clock();
        cpu_time_used1 += ((double)(end - start)) / CLOCKS_PER_SEC;

        start = clock();
        Memoization(C, weights, values, i, memo);
        end = clock();
        cpu_time_used2 += ((double)(end - start)) / CLOCKS_PER_SEC;

        start = clock();
        Dynamic(C, weights, values, i);
        end = clock();
        cpu_time_used3 += ((double)(end - start)) / CLOCKS_PER_SEC;

        printf("%d	%d	%f	%f	%f
", i, C, cpu_time_used1 / 3.0, cpu_time_used2 / 3.0, cpu_time_used3 / 3.0);

        for (int j = 0; j <= i; j++) {
            free(memo[j]);
        }
        free(memo);
    }

    return 0;