题目描述

背包问题给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值给定一个正数bag，表示一个载重bag的袋子，装的物品不能超过这个重量返回能装下的最大价值

暴力递归

解题思路

要向获得最大值,其实就是在每一个物品之中做选择.
找出选择的最优解.
有了这个思路,那么递归就是在一个商品上选和不选去比较最大值,
递归的就已经出来了.
然后讨论base case 了,
一.weights 数组越界,没有商品可以选了,肯定是个结束条件
二.背包没有空间去装了,也是个base case 要返回的.
递归的结构和base case 都有了,直接看代码吧

代码演示

 /*** 获取最大值* @param w* @param v* @param bag* @return*/public static int maxValue(int[]w,int[]v,int bag){//参数校验,题目中其实已经对数据限制了,if (null == w || v == null || w.length != v.length || w.length == 0 || bag < 0 ){return 0;}return process(w,v,0,bag);}/*** 递归方法* @param weights 不同商品重量* @param values 商品价值 和重量一一对应* @param index 下标值 代表要选第几号商品了* @param bag 背包容量* @return*/public static int process(int[]weights,int[]values,int index,int bag){//base case 越界if (index == weights.length){return 0;}//返回-1 为了对无效选择做判断if (bag < 0){return -1;}//选和不选两个状态//不选的情况int p1 = process(weights,values,index + 1,bag);//选的情况int p2 = 0;//选的情况int next = process(weights,values,index + 1,bag - weights[index]);// 返回 -1  代表 bag - weights[index] 这个选择是无效 的.//也就是index 这个选择是无效的 就不能执行if 里面的//也可以先判断bag - weights[index] < 0 来判断,小于0 就不进行递归// 和利用返回值判断是一样的,随你心情if (next != -1){p2 = values[index] + next;}//选择最大值return Math.max(p1,p2);}

动态规划

解题思路

动态规划,其实就是对递归过程的抽象化.把递归放在一张表中
递归改动态规划:
首先要看递归的base case,这样能知道如何初始化值.
其次要看递归过程,
下面代码演示下

代码演示

  /*** 动态规划* @param w* @param v* @param bag* @return*/public static int dp(int[]w,int[]v,int bag){//参数校验if (null == w || v == null || w.length != v.length || w.length == 0 || bag < 0 ){return 0;}int N  = w.length;//动态规划表//初始化的过程 看递归的base case  index == N 是0,//数组本身就是0 因此不需要显示的初始化int[][] dp = new int[N + 1][bag + 1];//看递归过程,来决定如何改动态规划//由于base case 是到N 开始返回的//所以dp 要从N - 1 开始填充值.//因此从N - 1开始循环for (int i = N - 1;i >= 0;i--){for (int k = 0; k <= bag;k++){// int p1 = process(weights,values,index + 1,bag);// 这一行代码 就是递归改动态规划,int p1 = dp[i + 1][k];//选的情况int p2 = 0;// int next = process(weights,values,index + 1,bag - weights[index]);// 看下两着是不是一样 只是一个递归 一个表中取.int next = bag - w[i] < 0 ? -1 : dp[i + 1][bag - w[i]];if (next != -1){p2 = v[i] + next;}dp[i][k] = Math.max(p1,p2);}}return dp[0][bag];}