0/1 背包问题求解算法 - 深度优先搜索实现

该代码实现了一个暴力的 0/1 背包问题求解算法。具体来说，通过深度优先搜索的方式枚举每个物品的选择与不选择，从而得到所有可能的背包组合，并计算其总价值，最终输出最大总价值。

代码中定义了几个全局变量，分别是物品个数 n、每个物品的重量 w 和价值 v、背包容量 W，以及最大总价值 maxV。其中，dfs 函数表示进行深度优先搜索的函数，参数 i 表示当前搜索到的物品下标，cw 表示当前已经放入背包的物品总重量，cv 表示当前已经放入背包的物品总价值。搜索过程中，首先判断是否已经搜索完所有物品（即 i 是否等于 n），如果是，则更新最大总价值 maxV。然后分别尝试选择当前物品或不选择当前物品，通过递归的方式继续搜索下一个物品，直到搜索完所有物品。

在主函数中，首先输入物品个数 n、每个物品的重量 w 和价值 v、背包容量 W。然后初始化最大总价值 maxV 为 0，调用 dfs 函数进行搜索。最后输出最大总价值 maxV。

需要注意的是，由于该算法是暴力搜索，时间复杂度很高，因此只适用于物品个数较少的情况。当物品个数 n 较大时，建议使用其他更高效的算法（如动态规划）。

#include <stdio.h>

#define MAXN 20

int n; // 物品个数
int w[MAXN]; // 物品重量
int v[MAXN]; // 物品价值
int W; // 背包容量
int maxV; // 最大价值

void dfs(int i, int cw, int cv) {
    if (i == n) {
        if (cv > maxV) {
            maxV = cv;
        }
        return;
    }
    dfs(i + 1, cw, cv); // 不选择第 i 个物品
    if (cw + w[i] <= W) {
        dfs(i + 1, cw + w[i], cv + v[i]); // 选择第 i 个物品
    }
}

int main() {
    printf("Please input the number of items: ");
    scanf("%d", &n);
    printf("Please input the weight and value of each item:\n");
    int i;
    for (i = 0; i < n; ++i) {
        scanf("%d %d", &w[i], &v[i]);
    }
    printf("Please input the capacity of the knapsack: ");
    scanf("%d", &W);
    maxV = 0;
    dfs(0, 0, 0);
    printf("The maximum value is: %d\n", maxV);
    return 0;
}