一：题目：

背包问题

问题：两个数组 一个重量数组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];}}