n个物品有重量W={w 1,…,wn}和价值P={p 1,…,pn}, 有一容量为C的背包（其中wi ,p I, CZ+）。如何选择物品装入背包，是装入物品的价值最大？ 要求： 1）编写算法，按单位重量的价值由大到小排序，重新编号。 2）编写算法int InitProfit()求出初始解bestp； 3）编写算法float Bound(int i)求出上界值； 4）编写回溯算法void Backtrack(int t)求出最优解和最优值。 5）实例：n=11, wi随机产生，范围1~20；p i随机产生，范围10~30；C等于所有物品重量和的4/5（取整数）。编写程序，将结果打印到文件（Knapsack.txt）。C语言实现

以下是使用C语言实现的完整代码，包括排序算法、初始解算法、上界计算算法和回溯算法，以及主函数用于生成随机数据和输出结果到文件中。

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

void sortItems(int n, int int w[], int p[], int v[], int id[]);
int InitProfit(int n, int w[], int p[], int C);
float Bound(int i, int n, int w[], int p[], int C, int profit);
void Backtrack(int t, int n, int w[], int p[], int C, int id[], int x[], int &bestp, int bestx[]);

int main() {
    int n = 11;
    int w[n + 1];
    int p[n + 1];
    int v[n + 1];
    int id[n + 1];
    int C, bestp = 0;
    int bestx[n + 1];
    int x[n + 1];

    // 生成随机数据
    srand((unsigned) time(NULL));
    for (int i = 1; i <= n; i++) {
        w[i] = rand() % 20 + 1;
        p[i] = rand() % 21 + 10;
    }
    C = 4 * (w[1] + w[2] + w[3] + w[4] + w[5]) / 5;

    // 排序
    sortItems(n, w, p, v, id);

    // 求初始解
    bestp = InitProfit(n, w, p, C);

    // 回溯搜索
    Backtrack(1, n, w, p, C, id, x, bestp, bestx);

    // 输出结果到文件
    FILE *fp;
    fp = fopen("Knapsack.txt", "w+");
    fprintf(fp, "n = %d, C = %d\n", n, C);
    fprintf(fp, "w = {");
    for (int i = 1; i <= n; i++) {
        fprintf(fp, "%d", w[i]);
        if (i < n) {
            fprintf(fp, ", ");
        }
    }
    fprintf(fp, "}\n");
    fprintf(fp, "p = {");
    for (int i = 1; i <= n; i++) {
        fprintf(fp, "%d", p[i]);
        if (i < n) {
            fprintf(fp, ", ");
        }
    }
    fprintf(fp, "}\n");
    fprintf(fp, "bestp = %d\n", bestp);
    fprintf(fp, "bestx = {");
    for (int i = 1; i <= n; i++) {
        fprintf(fp, "%d", bestx[i]);
        if (i < n) {
            fprintf(fp, ", ");
        }
    }
    fprintf(fp, "}\n");
    fclose(fp);

    return 0;
}

void sortItems(int n, int w[], int p[], int v[], int id[]) {
    for (int i = 1; i <= n; i++) {
        v[i] = p[i] / w[i];
        id[i] = i;
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (v[i] < v[j] || (v[i] == v[j] && id[i] > id[j])) {
                int temp = v[i];
                v[i] = v[j];
                v[j] = temp;
                temp = w[i];
                w[i] = w[j];
                w[j] = temp;
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
                temp = id[i];
                id[i] = id[j];
                id[j] = temp;
            }
        }
    }
}

int InitProfit(int n, int w[], int p[], int C) {
    int profit = 0, weight = 0;
    for (int i = 1; i <= n; i++) {
        if (weight + w[i] <= C) {
            weight += w[i];
            profit += p[i];
        } else {
            profit += (C - weight) * p[i] / w[i];
            break;
        }
    }
    return profit;
}

float Bound(int i, int n, int w[], int p[], int C, int profit) {
    float bound = profit;
    int weight = 0;
    for (int j = i; j <= n; j++) {
        if (weight + w[j] <= C) {
            weight += w[j];
            bound += p[j];
        } else {
            bound += (C - weight) * p[j] / w[j];
            break;
        }
    }
    return bound;
}

void Backtrack(int t, int n, int w[], int p[], int C, int id[], int x[], int &bestp, int bestx[]) {
    if (t > n) {
        if (bestp < x[0]) {
            bestp = x[0];
            for (int i = 0; i <= n; i++) {
                bestx[i] = x[i];
            }
        }
        return;
    }
    if (x[0] + Bound(t, n, w, p, C, x[0]) <= bestp) {
        return;
    }
    x[t] = 1;
    int weight = 0;
    int profit = 0;
    for (int i = 1; i <= t; i++) {
        if (x[i] == 1) {
            weight += w[id[i]];
            profit += p[id[i]];
        }
    }
    if (weight <= C) {
        Backtrack(t + 1, n, w, p, C, id, x, bestp, bestx);
    }
    x[t] = 0;
    Backtrack(t + 1, n, w, p, C, id, x, bestp, bestx);
}