商业网站建设与维护方案书,别人的做网站,cms全称,有网站源程序怎么做网站后台文章目录01背包基础 #xff08;二维数组#xff09;思路递推公式初始化遍历顺序一维dp数组#xff08;滚动数组#xff09;一维数组的递推公式遍历顺序LeetCode 416. 分割等和子集思路总结01背包基础 #xff08;二维数组#xff09;
思路
根据动态规划五部进行分析二维数组思路递推公式初始化遍历顺序一维dp数组滚动数组一维数组的递推公式遍历顺序LeetCode 416. 分割等和子集思路总结01背包基础 二维数组
思路
根据动态规划五部进行分析先进行参数和下标的初始化 由于是背包探索我们用二维数组 创建一个 dp[i][j] i是指第几个书包j是指背包最多能容下的体积 然后确定递推公式 递推公式
这道题递推公式的展开从两个方面 一个是尺寸比书包小可以放进去 一个是尺寸比书包放不进去
不放物品i 由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以被背包内的价值依然和前面相同。)放物品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]);
初始化
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。
// 正序遍历
for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}遍历顺序
在二维数组中无论是先遍历物品 后遍历背包 或者 先遍历背包后遍历物品都能够达成目的 不过在后序的一维数组中完成背包问题就固定下来了 先遍历物品后遍历书包。
一维dp数组滚动数组
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是
dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。
一维数组的递推公式 dp[j]可以通过dp[j - weight[i]]推导出来dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。 dp[j - weight[i]] value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。也就是容量为j的背包放入物品i了之后的价值即dp[j] 此时dp[j]有两个选择一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]即不放物品i一个是取dp[j - weight[i]] value[i]即放物品i指定是取最大的毕竟是求最大价值 dp[j] max(dp[j], dp[j - weight[i]] value[i]);遍历顺序
与二维数组不同 先物品再背包 背包遍历要求 倒序遍历因为这样就可以保证每一个物品只放一次
for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}LeetCode 416. 分割等和子集
思路
这里运用了 01背包的思路 我的做法是采用了一维数组的方式做的
class Solution {public boolean canPartition(int[] nums) {if(numsnull|| nums.length0) return false;int nnums.length;int sum0;for(int num: nums){ sum num;}if( sum%2!0) return false;int target sum/2;int dp[] new int [target1];for( int i0;in;i){for( int jtarget;j nums[i];j--){dp[j] Math.max( dp[j],dp[j-nums[i]]nums[i]);}}return dp[target] target;}
}总结
恢复更新了之前在返校临开学也没有状态就休息了一段时间
