写用回溯法求解0/1背包问题的代码 1)可分步骤实现，先编写子集树回溯代码，再加入背包代码，再加入约束函数和限界函数。 2)输出最优解和解向 C++代码

1) 分步骤实现：

// 子集树回溯代码
void backtrack(int i, int profit, int weight) {
if (weight <= W && profit > maxprofit) {
maxprofit = profit;
for (int j = 1; j <= n; j++) bestx[j] = x[j];
}
if (i > n) return;
if (weight + w[i] <= W) {
x[i] = 1;
backtrack(i+1, profit+p[i], weight+w[i]);
x[i] = 0;
}
backtrack(i+1, profit, weight);
}

// 背包代码
int knapsack() {
int i, j;
for (i = 0; i <= W; i++) f[0][i] = 0;
for (i = 1; i <= n; i++) {
for (j = 0; j <= W; j++) {
if (w[i] > j) f[i][j] = f[i-1][j];
else f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+p[i]);
}
}
return f[n][W];
}

// 约束函数和限界函数
bool promising(int i, int profit, int weight) {
if (weight > W) return false;
int j, k;
float bound = profit;
k = weight;
for (j = i+1; j <= n; j++) {
if (k + w[j] > W) break;
k += w[j];
bound += p[j];
}
if (j <= n) bound += (W-k) * p[j]/w[j];
return bound > maxprofit;
}

void backtrack(int i, int profit, int weight) {
if (weight <= W && profit > maxprofit) {
maxprofit = profit;
for (int j = 1; j <= n; j++) bestx[j] = x[j];
}
if (promising(i, profit, weight)) {
x[i] = 1;
backtrack(i+1, profit+p[i], weight+w[i]);
x[i] = 0;
backtrack(i+1, profit, weight);
}
}

2) 输出最优解和解向的C代码：

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

#define MAXN 100
#define MAXW 1000

int n, W, maxprofit, p[MAXN+1], w[MAXN+1], f[MAXN+1][MAXW+1], x[MAXN+1], bestx[MAXN+1];

void backtrack(int i, int profit, int weight);
int knapsack();
bool promising(int i, int profit, int weight);

int main() {
printf("Enter the number of items and the capacity of the knapsack:\n");
scanf("%d%d", &n, &W);
printf("Enter the profits and weights of the items:\n");
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i], &w[i]);

// 计算最优解
maxprofit = knapsack();
printf("The maximum profit is %d.\n", maxprofit);

// 回溯求解最优解的解向
backtrack(1, 0, 0);
printf("The solution vector is:\n");
for (int i = 1; i <= n; i++) printf("%d ", bestx[i]);
printf("\n");

return 0;
}

void backtrack(int i, int profit, int weight) {
if (weight <= W && profit > maxprofit) {
maxprofit = profit;
for (int j = 1; j <= n; j++) bestx[j] = x[j];
}
if (promising(i, profit, weight)) {
x[i] = 1;
backtrack(i+1, profit+p[i], weight+w[i]);
x[i] = 0;
backtrack(i+1, profit, weight);
}
}

int knapsack() {
int i, j;
for (i = 0; i <= W; i++) f[0][i] = 0;
for (i = 1; i <= n; i++) {
for (j = 0; j <= W; j++) {
if (w[i] > j) f[i][j] = f[i-1][j];
else f[i][j] = max(f[i-1][j], f[i-1][j-w[i]]+p[i]);
}
}
return f[n][W];
}

bool promising(int i, int profit, int weight) {
if (weight > W) return false;
int j, k;
float bound = profit;
k = weight;
for (j = i+1; j <= n; j++) {
if (k + w[j] > W) break;
k += w[j];
bound += p[j];
}
if (j <= n) bound += (W-k) * p[j]/w[j];
return bound > maxprofit;
}