背包问题暴力搜索算法详解：深度优先搜索实现

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

该代码实现了背包问题的暴力搜索，通过深度优先搜索算法来枚举所有可能的组合情况，然后选出最优解。

具体实现思路：

定义全局变量n、w、v、W、maxV，分别表示物品个数、物品重量、物品价值、背包容量、最大价值。
定义dfs函数，其中i表示当前考虑到第i个物品，cw表示当前背包已装的重量，cv表示当前背包已装的价值。函数实现如下：

（1）如果i已经超过了物品个数n，则说明已经考虑完所有物品，比较当前背包价值是否比最大价值maxV大，如果是，更新maxV。

（2）不选择第i个物品，直接调用dfs(i+1, cw, cv)。

（3）选择第i个物品，如果当前背包的重量加上第i个物品的重量不超过背包容量W，则调用dfs(i+1, cw+w[i], cv+v[i])。

在main函数中，依次读入物品的重量和价值，以及背包容量W。然后调用dfs函数，得到最大价值maxV，最后输出结果。

该算法的时间复杂度为O(2^n)，需要枚举所有可能的组合情况，因此对于物品个数较大的情况，该算法的效率较低。