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]值。

完整代码如下：