算法分析编程：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语言编写：

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

#define N 11    // 物品数量
#define MAX_WEIGHT 20   // 最大重量
#define MIN_WEIGHT 1    // 最小重量
#define MAX_VALUE 30    // 最大价值
#define MIN_VALUE 10    // 最小价值

int w[N], p[N];         // 物品重量和价值
int sorted_index[N];    // 按单位重量价值排序后的物品编号
int bestp[N];           // 当前最优解
int bestv = 0;          // 当前最优值
int c;                  // 背包容量

// 按单位重量价值由大到小排序
void sort_by_unit_value() {
    int i, j, temp;
    float unit_value[N];
    for(i = 0; i < N; i++) {
        unit_value[i] = (float)p[i] / w[i];
        sorted_index[i] = i;
    }
    for(i = 0; i < N-1; i++) {
        for(j = i+1; j < N; j++) {
            if(unit_value[sorted_index[i]] < unit_value[sorted_index[j]]) {
                temp = sorted_index[i];
                sorted_index[i] = sorted_index[j];
                sorted_index[j] = temp;
            }
        }
    }
}

// 求出初始解bestp
int init_profit() {
    int i = 0, weight = 0;
    while(weight + w[sorted_index[i]] <= c && i < N) {
        bestp[sorted_index[i]] = 1;
        weight += w[sorted_index[i]];
        bestv += p[sorted_index[i]];
        i++;
    }
    return i;
}

// 求出上界值
float bound(int i, int weight, int value) {
    float bound_value = value;
    while(i < N && weight + w[sorted_index[i]] <= c) {
        weight += w[sorted_index[i]];
        bound_value += p[sorted_index[i]];
        i++;
    }
    if(i < N)
        bound_value += (c - weight) * ((float)p[sorted_index[i]] / w[sorted_index[i]]);
    return bound_value;
}

// 回溯算法
void backtrack(int t, int weight, int value) {
    if(t == N) {
        // 更新最优解和最优值
        if(value > bestv) {
            int i;
            for(i = 0; i < N; i++)
                bestp[i] = p[i];
            bestv = value;
        }
        return;
    }
    // 尝试放入第t个物品
    if(weight + w[sorted_index[t]] <= c) {
        bestp[sorted_index[t]] = 1;
        backtrack(t+1, weight+w[sorted_index[t]], value+p[sorted_index[t]]);
        bestp[sorted_index[t]] = 0;
    }
    // 不放入第t个物品
    if(bound(t+1, weight, value) > bestv)
        backtrack(t+1, weight, value);
}

int main() {
    srand(time(NULL));
    int i;
    c = 0;
    for(i = 0; i < N; i++) {
        w[i] = rand() % (MAX_WEIGHT - MIN_WEIGHT + 1) + MIN_WEIGHT;
        p[i] = rand() % (MAX_VALUE - MIN_VALUE + 1) + MIN_VALUE;
        c += w[i];
    }
    c = c * 4 / 5;
    sort_by_unit_value();
    int i_end = init_profit();
    printf("初始解：");
    for(i = 0; i < N; i++)
        printf("%d ", bestp[i]);
    printf("\n");
    backtrack(i_end, 0, bestv);
    printf("最优解：");
    for(i = 0; i < N; i++)
        printf("%d ", bestp[i]);
    printf("\n");
    printf("最优值：%d\n", bestv);
    FILE *fp;
    fp = fopen("Knapsack.txt", "w");
    fprintf(fp, "初始解：");
    for(i = 0; i < N; i++)
        fprintf(fp, "%d ", bestp[i]);
    fprintf(fp, "\n");
    fprintf(fp, "最优解：");
    for(i = 0; i < N; i++)
        fprintf(fp, "%d ", bestp[i]);
    fprintf(fp, "\n");
    fprintf(fp, "最优值：%d\n", bestv);
    fclose(fp);
    return 0;
}

上述程序通过调用rand()函数生成随机数来模拟n个物品的重量和价值，然后按照单位重量价值由大到小排序，并求出初始解和上界值。最后调用回溯算法求解最优解和最优值，并将结果输出到文件中。