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语言编程。

这是一道经典的背包问题，可以采用回溯算法进行求解。具体的算法步骤如下：

1. 按照单位重量的价值从大到小排序，重新编号。

2. 初始化bestp为0，表示初始解为0。

3. 计算上界值bound，用于剪枝。

4. 从第1个物品开始，依次考虑每个物品是否放入背包中：

a. 如果当前物品已经放不下了，直接返回。

b. 如果当前物品可以放入背包中，尝试放入背包并更新当前价值。

c. 如果当前价值加上剩余物品的最大价值小于bestp，说明当前解已经不可能是最优解，直接返回。

d. 如果当前价值大于bestp，更新bestp。

5. 回溯算法结束后，将最优解和最优值输出到文件中。

下面是具体的算法实现：

相关问题

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）。

为了方便起见，我们将物品按照单位重量的价值由大到小排序，并重新编号。设物品的编号为1至n，重量为w1至wn，价值为p1至pn，背包的容量为C。

1. 排序算法

设v[i]表示第i个物品的单位重量价值，将物品按照v[i]从大到小排序，相同的按照编号从小到大排序。

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])) {
swap(v[i], v[j]);
swap(w[i], w[j]);
swap(p[i], p[j]);
swap(id[i], id[j]);
}
}
}
}

2. 初始解算法

初始解可以选择贪心算法，将物品按照单位重量价值从大到小装入背包，直到无法再装下为止。

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;
}

3. 上界计算算法

设物品i至n的总重量为w[i..n]，总价值为p[i..n]，则上界为当前背包的价值加上剩余物品的单位重量价值之和乘以剩余容量，即：

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;
}

4. 回溯算法

回溯算法的框架如下：

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);
}

其中，x[i]表示第i个物品是否被放入背包中，bestx[i]表示最优解对应的x[i]值。

完整代码如下：

算法分析编程：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个物品的重量和价值，然后按照单位重量价值由大到小排序，并求出初始解和上界值。最后调用回溯算法求解最优解和最优值，并将结果输出到文件中。