自己做开奖网站,莱芜金点子电子版报纸,公众号入口官网,上海交通建设工程信息服务平台动态规划 文章目录 一、01背包问题二、分割等和子集总结 一、01背包问题
1.在有限的背包内放入最高价值的东西 2.二维数据和一维数据都可以解决 3.二维数据#xff0c;递推公式为dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]]value[i])#xff0c;分为两个状态#xff0… 动态规划 文章目录 一、01背包问题二、分割等和子集总结 一、01背包问题
1.在有限的背包内放入最高价值的东西 2.二维数据和一维数据都可以解决 3.二维数据递推公式为dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]]value[i])分为两个状态放入第i个物品和不放入第i个物品取其中的最大值。表示遍历到第i个物品时可以得到的最大价值当前i的最大价值由i上边和左边的物品决定。递推公式不算很难难点在于数组初始化以及遍历顺序。 4.一维数组也就是滑动数组当前遍历结果受到上层结果影响。递推公式为dp[j] max(dp[j], dp[j-weight[i]]value[i])表示在j容量下可以获得的最大价值。因为是一维数组同时当前的遍历结果受到上一层的影响所以遍历顺序需要从后往前。如果从前往后的话上层遍历结果要先于当前遍历物品改变所以要从后往前。
二、分割等和子集
01背包问题将问题抽象为01背包问题。
class Solution {
public:bool canPartition(vectorint nums) {//两个子集的元素和相同也就是如果能组成一个sum/2那其他的元素也能组成sum/2//sum/2相等于背包容量//1.dp数组及下标含义vectorintdp(10001, 0);int sum 0;for (int i 0; i nums.size(); i) {sum nums[i];}if (sum % 2 1) return false;int target sum / 2;for (int i 0; i nums.size(); i) {for (int j target; j nums[i]; j--) {dp[j] max (dp[j], dp[j - nums[i]] nums[i]);}}if (dp[target] target) return true;return false;}
};总结
有点宕机感觉总有点不对某个节点一直没整明白明天再好好理一下 学习时间90min。 学习资料《代码随想录》。
