旅行社网站策划,做网站的标签什么意思,wordpress hhvm,wordpress文章部分显示背包问题
01背包问题#xff1a;每件物品只能用一次完全背包问题#xff1a;每件物品可以使用无数次
01背包问题
暴力解法#xff1a;每一件物品其实只有两个状态#xff0c;取或者不取#xff0c;所以可以使用回溯法搜索出所有的情况#xff0c;那么时间复杂度就是 o…背包问题
01背包问题每件物品只能用一次完全背包问题每件物品可以使用无数次
01背包问题
暴力解法每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是 o ( 2 n ) o(2^n) o(2n)这里的n表示物品数量。动态规划dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。对于物品i 不放物品i由dp[i - 1][j]可知即从下标为[0到i-1]的物品里任意取放进容量为j的背包价值总和最大是多少。也可以理解为背包容量为j里面不放物品i的最大价值此时dp[i][j]dp[i - 1][j]。放物品i由dp[i - 1][j - weight[i]]可知dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值得到递推公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 初始化 当j为0的时候不管不放物品背包中的价值都是0当i为0的时候即每次选择0物品放入各个大小的背包中当且仅当jweight[i]才会有value[i]的价值
01背包-滚动数组
对于二维dp数组dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);如果在i维度进行叠加即将i-1上的所有值拷贝到i上递归公式变成dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);因此将二位dp数组变成一维数组得到递归公式dp[j] max(dp[j],dp[j-weight[i]]value[i]) 一维dp数组的含义重量为j的背包中装的价值最大的物品是dp[j] 二维dp数组的遍历顺序是从上到下从左到右一维dp数组的遍历顺序 i0-》weight.length-1jbagweight-》0j不是0-》bagweight是因为如果是正序遍历背包重量j中的价值dp[j]可能等于dp[j-weight[i]]value[i]而dp[j-weight[i]]可能就已经蕴含了value[i]将重复计算j倒序遍历是为了保证物品i只被放入一次i的正序遍历是为了保证所有的物品都被判断过
LC416分割等和子集(未掌握)
只给定了一个数组因此这个数组即是weight又是valueif(jweight[i]) dp[j] dp[j];else dp[j] Math.max(dp[j],dp[j-weight[i]]value[i])可以转换为for(int j n;jweight[i];j–)剪枝操作在第二层循环中加入if(dp[target]target) return true;代码
