介绍
给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是
，其价值为
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
背包问题是具有许多应用的组合优化问题
背包问题
在背包问题中，我们有一组物品。每个物品都有重量和价值：
我们想将这些物品放入背包。但是，它有一个重量限制：
因此，我们需要选择总重量不超过重量限制的物品，并且其总价值达到最高。 例如，上述示例的最佳解决方案是选择5kg和6kg物品，它们在重量限制内的最大值为40元。
背包问题有几种变化，我们将重点介绍0-1背包问题。在0-1背包问题中，必须选择每个物品或将其留在后面。我们不能取一部分物品。另外，我们不能多次取一件物品。
数学公式
现在让我们以数学符号形式化0-1背包问题。给定一组n个物品和重量限制W，我们可以将优化问题定义为：
这个问题是NP完全难题。因此，目前尚无多项式时间算法可以解决。但是，对于此问题，可以使用动态规划算法思路来解决。
递归算法
使用递归公式来解决此问题：
在该公式中， 是重量限制为w的n个物品的最优解。它是以下两个值中的最大值：
重量限制为w的（n-1）个物品的最优解（不包括第n个项目）
第n个物品的值加上（n-1）个物品的最优解和w减去第n个物品的权重（包括第n个物品）
如果第n项的重量大于当前的重量限制，则不包括在内。因此，它属于上述两种情况的第一类。
Java中实现此递归公式代码：
在每个递归步骤中，我们需要评估两次最优解决逻辑，因此，此递归解决方案的运行时间为O（）。
动态规划算法
动态规划思路是一种用于线性化，指数级递增的编程算法的思路，这个思路是存储子问题的结果，这样我们以后就不必重新计算它们了。
我们还可以通过动态规划解决0-1背包问题。要使用动态规划中，我们使用自下而上的方法来计算最佳解决方案：
/**
* @param w : 已知物品重量数组集合
* @param v : 已知物品价值数组集合
* @param n ： 最大价值，0 表示不要求
* @param W : 最大重量，0 表示不要求
* @author 油腻的Java
* @date 2019/11/5
* @return
*/
public int knapsackDP(int[] w, int[] v, int n, int W) {
if (n <= 0 || W <= 0) {
return 0;
}
/**
* 创建临时数组
*/
int[][] m = new int[n + 1][W + 1];
for (int j = 0; j <= W; j++) {
m[0][j] = 0;
}
/**
* 遍历n和W,
*/
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (w[i - 1] > j) {
//对m数组进行赋值
m[i][j] = m[i - 1][j];
} else {
//求最大值
m[i][j] = Math.max(m[i - 1][j], m[i - 1][j - w[i - 1]] + v[i - 1]);
}
}
}
return m[n][W];
}
在代码中，我们在商品价值n和重量限制W上有一个嵌套循环。因此，它的运行时间为O（nW）。
单元测试
最后针对各自的场景做了一下单元测试
同时满足价格，重量最大化
最大重量最优解
最大价格最优解
结论
本文通过编写递归算法、动态规划算法来解决背包0-1问题，以及测试相应的单元测试，希望在背包算法对你有新的认知。
