首先，我们先要知道什么是01背包问题。
01背包问题：
给定n件不可分割的物品和⼀个背包。物品i的重量是w[i]，其价值为v[i]，背包的容量 为c。问应如何选择装⼊背包中的物品，使得装⼊背包中的物品在不超过背包容量的情况下总价值最⼤？ 在选择装⼊背包的物品时，对每种物品i只有两种选择，即装⼊背包【1】和不装⼊背包【0】不能将 物品装⼊背包多次，也不能只装⼊商品的⼀部分（商品不可分割）。这就是经典的0-1背包问题。
首先，定义两个数组：wt_goods和val_goods，分别表示存放物品的重量和价值的数组。
例：
static int wt_goods[] = {1,2,3};
static int val_goods[] = {6,10,12};随后，我们定义一下背包容量：
const int bag_capacity = 5;那么，根据问题的描述，我们首先能够想到的算法便是贪心算法。即每次找局部最优解，那么，我们便很容易的能够想到：将物品进行 （价值/重量） 的运算，每次将比重大的放入背包，这样的话不就行了吗？
那么，事实如此吗，我们来看，倘若将上面的例子进行这样的运算，那么我们便能够很容易的得到：
物品1:6，物品2:5，物品3：4，那么我们应该放入物品1和2，结果是16。但是实际上，我们都能够很容易的看出，如果放入物品2和物品3，那么背包容量正好够用，且最后答案是22，明显要大于我们刚刚的算法，因此我们要注意：
贪心算法的局部最优解并不能在所有时候都决定全局最优解，但是在大部分实际情况中，即使达不到全局最优也能够接近全局最优，因此大多数工程实例中，贪心算法仍然是最优先考虑的一种算法。
但是这里我们要求全局最优，那么我们便不能使用贪心算法了。
分析：在01背包问题中，我们可以将大问题拆分成一个个子问题，且子问题之间有相互影响，因此我们很能够想到的便是动态规划的思想。
那么，我们来推一下公式吧：
首先，在01背包中，无非就是两种情况：放或不放，如果放，则背包容量减去物品重量，物品的索引移到下一个位置。如果不放，则背包容量不变，物品索引移动到下一个位置。我们则需要判断这两种状态的最大值，因此，便可以得出：
static int Max(int res1,int res2) {return (res1 > res2) ? res1 : res2;
}//分析：01背包无非是两种情况：放或不放，因此比较的是放或不放两者中哪个值最大
static int bestValue01(int index, int c) {//不放//int res1 = bestValue01(index - 1, c);//放//int res2 = bestValue01(index - 1, c - wt_goods[index]);//归的条件：无法选物品或无法装物品，返回0if (index < 0 || c <= 0) {return 0;}//进一步优化：在背包中还有空间的情况下，进行递的操作，也就是判断放或不放的最大值并记录返回int res = bestValue01(index - 1, c);if (c >= wt_goods[index]) {res = Max(res, val_goods[index] + bestValue01(index - 1, c - wt_goods[index]));}return res;
}static int knapsack01() {return bestValue01(sizeof(val_goods) / sizeof(val_goods[0]) - 1, bag_capacity);
}
然后我们来测试一下：
void main() {int result = knapsack01(sizeof(val_goods) / sizeof(val_goods[0]),bag_capacity);printf("%d", result);return 0;
}最后结果：
与预期无误，证明我们没有问题。
很显然，上述问题是通过递归来实现的，这就很容易出现重复访问的情况，因此我们很容易想到的便是引入数组来进行记忆优化搜索。
//引入数组进行优化
static int bestValue02(int index,int c,int** mem) {if (index < 0 || c <= 0) {return 0;}if (mem[index][c] != -1) {return mem[index][c];}int res = bestValue02(index - 1, c,mem);if (c >= val_goods[index]) {res = Max(res, val_goods[index] + bestValue02(index - 1, c - wt_goods[index],mem));}return res;
}static int knapsack02() {int n = sizeof(val_goods) / sizeof(val_goods[0]);int** mem = malloc(n * sizeof(int*));for (int i = 0; i < n; i++) {mem[i] = malloc((bag_capacity + 1) * sizeof(int));for (int j = 0; j <= bag_capacity; j++) {mem[i][j] = -1;}}int result = bestValue02(n - 1, bag_capacity, mem);// 释放内存for (int i = 0; i < n; i++) {free(mem[i]);}free(mem);return result;
}最后测试结果：
符合预期，正确。
说完了两种最基础的递归方法，那么接下来我们就正式的使用DP算法再进行进一步的优化：
首先，我们可以有这么一张表：
分别表示当前背包的容量和物品，首先当背包容量为0时，无论什么物品都放不进去，因此第一列都是0。
当我们目前只有一个物品时，可以很容易的填出第一行。
当我们有两个物品时，就要进行判断：
1.背包空间是否足够 放入物品
2.背包空间足够，放入新物品后，与上一次相比，哪个更大，大则更新，否则维持上次结果。
紧接着，现在我们遍历到了三个物品，前面依旧维持上一次的结果，当空间足够放入后，进行判断：当前放入后是否比之前保存的值大，大则更新。（如图中，当为3时，上次的最优解为16，而如果放入，则为12（当前的值加上减去了物品重量后保存的值比如这里，放入后为12+0（减去物品重量3后，0位置上次保存的最优解为0） = 12）因此不更新，维持上次结果。当空间为4时，放入，则为18（12+6），比16大，更新）
于是，我们就更新完了整个表，返回表的最右下角的值作为结果。
好了，模拟过程完毕，接下来写代码验证。
int knapsackDP(int n, int c) {// 分配内存：创建二维数组 DP，行数为物品数量 n，列数为背包容量 c+1int** DP = malloc(n * sizeof(int*));for (int i = 0; i < n; i++) {DP[i] = malloc((c + 1) * sizeof(int));}// 初始化第一行：根据背包容量和第一个物品的重量来决定是否放入物品for (int j = 0; j <= c; j++) {DP[0][j] = (j >= wt_goods[0]) ? val_goods[0] : 0;}for (int i = 1; i < n; i++){for (int j = 0; j <= c; j++) {//先记录上一次放的最大值 DP[i][j] = DP[i - 1][j];//如果当前背包容量比当前物品的重量大if (j >= wt_goods[i]) {//判断当前状态和放入后加上之前的背包中的状态比较，大的则采纳DP[i][j] = Max(DP[i][j], val_goods[i] + DP[i - 1][j - wt_goods[i]]);}}}// 获取结果值，即最大价值int result = DP[n - 1][c];// 释放内存for (int i = 0; i < n; i++) {free(DP[i]);}free(DP);return result;}最后测试一下：
与预期相符，说明正确。
好了，关于01背包的问题就说到这里了，觉得有用的话请点赞收藏~
