7.0-1背包问题：容量为72的背包，要装入3种重量为25,40,30的物品，它 们的价值分别为50,120,120，如何选择物品使得装入背包的物品的价值最 大。用回溯法求解该0-1背包问题，画出其搜索过程并求出最优解和最优值。

回溯法是一种穷举搜索方法，可以用于解决背包问题。具体步骤如下：

1. 每次选择一个物品，将其放入背包中，更新当前背包容量和已选物品的总价值。
2. 如果背包容量不足以装下任何一个物品，或者所有物品已经选择完毕，则返回上一层。
3. 对于剩余未选择的物品，递归调用步骤1和2，直到所有物品都选择完毕。

根据以上步骤，可以画出回溯法搜索过程的树形图如下：

                                            (0, 0)
                                    /         |         \
                            (25, 50)    (40, 120)    (30, 120)
                           /   \        /   \         /    |    \
                (65, 120) (40, 50) (40, 120) (5, 50) (30, 120) (2, 50)    
                    |        |        |       |         |       |
               (72, 170) (72, 120) (72, 170) (72, 120) (72, 170) (72, 120)

其中，节点表示当前状态（剩余背包容量，已选物品总价值），括号中数字表示选择的物品重量和价值。

从根节点开始，递归调用，可以得到所有可能的解，其中满足背包容量与选取的物品重量和相等的解即为最优解。根据上述搜索过程，可以得到最优解为选择两个重量为40和一个重量为30的物品，总价值为410。

注：为了简洁起见，下面的代码中省略了一些中间变量的声明和计算过程。

#include <iostream>
using namespace std;

int w[] = { 25, 40, 30 }; // 物品重量数组
int v[] = { 50, 120, 120 }; // 物品价值数组

int n = 3; // 物品数量
int max_w = 72; // 背包容量

int best_v = 0; // 最优价值
int x[100]; // 最优解数组
int cur_w = 0; // 当前背包容量
int cur_v = 0; // 当前已选物品总价值
int cnt = 0; // 记录搜索次数

void backtrack(int t) { // 参数t表示当前搜索到第几个物品
    if (t == n) { // 所有物品均已选择完毕
        if (cur_v > best_v && cur_w <= max_w) { // 更新最优解和最优价值
            best_v = cur_v;
            for (int i = 1; i <= n; i++) x[i] = y[i];
        }
        cnt++;
        return;
    }
    // 不选第t个物品
    backtrack(t + 1);
    // 选择第t个物品
    if (cur_w + w[t] <= max_w) { // 当前背包容量足以装下第t个物品
        cur_w += w[t]; // 更新当前背包容量
        cur_v += v[t]; // 更新当前已选物品总价值
        y[t] = 1; // 标记选择的物品
        backtrack(t + 1);
        cur_w -= w[t]; // 恢复当前背包容量
        cur_v -= v[t]; // 恢复当前已选物品总价值
        y[t] = 0; // 取消选择的物品
    }
}

int main() {
    backtrack(0);
    cout << "best_v = " << best_v << endl; // 输出最优价值
    cout << "x = "; // 输出最优解
    for (int i = 1; i <= n; i++) cout << x[i] << " ";
    cout << endl << "cnt = " << cnt << endl; // 输出搜索次数
    return 0;
}