背包问题暴力求解算法：C语言实现及详解

#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[MAXN]: 物品重量数组，MAXN 为物品个数的最大值，这里设为 20
  • v[MAXN]: 物品价值数组
  • W: 背包容量
  • maxV: 最大价值

• dfs 函数：

  • 该函数用于进行深度优先搜索，递归枚举所有选择方案。
  • 参数 i: 当前考虑的物品序号
  • 参数 cw: 当前背包中物品的总重量
  • 参数 cv: 当前背包中物品的总价值
  • 如果 i == n，说明已经遍历完所有物品，将当前的 cv 与 maxV 比较，更新最大价值。
  • 否则，分别考虑两种情况：
    • 不选择第 i 个物品，递归调用 dfs(i + 1, cw, cv)
    • 选择第 i 个物品，判断背包容量是否足够，如果足够则递归调用 dfs(i + 1, cw + w[i], cv + v[i])

• 主函数：

  • 首先输入物品个数、每个物品的重量和价值、背包容量。
  • 调用 dfs(0, 0, 0) 函数开始深度优先搜索，从第一个物品开始遍历。
  • 最后输出最大价值 maxV。

算法分析：

该代码的时间复杂度为 O(2^n)，因为要枚举所有可能的方案，每个物品都有两种选择（选或不选）。因此，对于物品个数较大的情况，该算法效率较低，需要采用其他优化方法，如动态规划等。