一：题目：
背包问题
问题：两个数组 一个重量数组W 一个 价值数组 V 一个背包 bag ，返回不超过背包容量返回最大价值
二：暴力解法
思路：暴力遍历，思路就是递归的时候 按 选或者不选 当前 物品，如果，这样就会产生 w 数组个数次方个解，也就是所有解，遍历返回条件就是如果bag 减去当前物品的重量小于0 说明当前物品就放不进去了就停止循环，没个递归都有将当前物品放进去和不放进去两个解，选最大的向上返回，最后得到的就是最优解。
三：动态规划解法
比如到 第N个物品 ，这个时候因为上面物品拿或不拿就可能会出现N-1次方次尝试，如果尝试的参数一样（背包剩余空间一样，并且都是第N个物品），这个时候就不用重复计算，对已经计算的结果做缓存就可以，基于这个思想，只要循环 w的个数*背包存储空间 次 就可以得出结果
int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
int[] values = { 5, 6, 3, 19, 12, 4, 2 };
int bag = 9;
1 最上面的一行代表背包剩余格子数
2 左边的代表 0到6个商品 总共7个
3 w 代表重量 v代表价值
开始推导
1 最下面一行 7 因为没有商品，所以最高价值都是0
2 倒数第二行6 物品重量是7 价值是 2 ，背包格子7之前，都不能放入背包，没有价值，7之后也只能放这一个物品
3 倒数第三行5 物品重量是1 价值是 4，当背包格子是1的时候就能装，装进去价值是4，在背包格子到8之前都能装6这个物品，当背包到8 ，装了5这个物品，还有7个背包空间，所以还能装6这个物品，价值则是2+4 = 6
4 倒数第四行 4 这个物品 也是按照逻辑做对比，其实上面都是按照这个逻辑的，只不过这里清晰写出来 ，首先判断当前背包容量是否能装 当前4这个物品，不能装价值就是0，能装也不能直接写0，还要看看5这个物品，当前背包容量的价值是多少，对比取最大。
5 按照这个计算策略，计算到最后 第一行最后一个 就是最优解27
代码
package 算法.动态规划.练习1;
/**
* 背包问题
* 参数
* w[] 重量
* v[] 价值
* 背包大小 int
*/
public class bag {
public static void main(String[] args) {
//1 返回背包模拟参数
int[] weights = {3, 2, 4, 7, 3, 1, 7};
int[] values = {5, 6, 3, 19, 12, 4, 2};
int bag = 9;
System.out.println(maxValue(weights, values, bag));
System.out.println(dp(weights, values, bag));
//2
}
/**
* 暴力解法
* @param w
* @param v
* @param bag
* @return
*/
private static int maxValue(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length||w.length==0) {
return 0;
}
return process(w, v, 0, bag);
}
private static int process(int[] w, int[] v, int index, int bag) {
if (index == w.length) {
return 0;
}
//不放当前
int p1 = process(w, v, index+1, bag);
//获取当前 价值
int p2 = 0;
//如果拿了当前的 还有地方就继续拿，如果小于0 说明当前都放不进去
if (bag-w[index] >= 0) {
//就继续拿
int next = process(w, v, index+1, bag-w[index]);
p2 = next+v[index];
}
return Math.max(p1, p2);
}
//动态规划
public static int dp(int[] w, int[] v, int bag) {
if (w == null || v == null || w.length != v.length || w.length == 0) {
return 0;
}
int N = w.length;
int[][] dp = new int[N + 1][bag + 1];
//从最下面一行开始
for (int index = N - 1; index >= 0; index--) {
//从左往右
for (int rest = 0; rest <= bag; rest++) {
//p1是不拿当前index的值 直接取下一个index rest背包大小情况下最大值
int p1 = dp[index + 1][rest];
int p2 = 0;
//如果rest剩余背包容量 减去当前 index 的重量（判断是否能放入背包） 放不进去返回-1 如果能放进去就取dp 放进去之后对应的解
int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
//如果能放进去 就累加 放不进去 p2 就是 0 相当于取p1 不放进去的情况（因为放进去就无解了）
if (next != -1) {
p2 = v[index] + next;
}
//把当前index 剩余背包容量rest 放不放进去当前的最优解放到数组里，以后index-1取 index 就直接取结果
dp[index][rest] = Math.max(p1, p2);
}
}
for (int index = 0 ; index <= N ; index++) {
//从左往右
for (int rest = 0; rest <= bag; rest++) {
System.out.print(dp[index][rest]+"|");
}
System.out.println(" ");
}
return dp[0][bag];
}
}