本文主要是介绍代码随想录算法训练营第四十二天| 01背包问题理论基础，416. 分割等和子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
理论基础：
带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili很多同学对背包问题的理解程度都处于一种黑盒的状态，及时这道题目在力扣上已经通过了，但其实有很多问题自己还是没有想清楚的，所以遇到下一道背包问题，已经还是想不明白，这次把我0-1背包给大家讲的通透，无论之前你是否学过背包问题，相信看完视频，你都会发现相见恨晚！！, 视频播放量 214097、弹幕量 1820、点赞数 5660、投硬币枚数 4875、收藏人数 2850、转发人数 666, 视频作者 代码随想录, 作者简介 我是Carl，哈工大师兄，先后在腾讯和百度从事一线技术研发的程序员，公众号「代码随想录」，相关视频：动态规划入门50题，[轻松掌握动态规划]5.最长公共子序列 LCS，一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵），【自制】01背包问题算法动画讲解，《算法零基础入门》动态规划 (一)，十几分钟了解动态规划01背包、完全背包！，算法讲解073【必备】背包dp-01背包、有依赖的背包，算法大佬——左程云老师带你彻底弄懂暴力递归→动态规划（背包问题、N皇后问题），动态规划入门：从记忆化搜索到递推，【动态规划】背包问题
https://www.bilibili.com/video/BV1cg411g7Y6/
416. 分割等和子集
刷不下去了 想放弃了 真难啊01背包
class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for(int num : nums) {sum += num;}//总和为奇数，不能平分if(sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < n; i++) {for(int j = target; j >= nums[i]; j--) {//物品 i 的重量是 nums[i]，其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）if(dp[target] == target)return true;}return dp[target] == target;}
}这篇关于代码随想录算法训练营第四十二天| 01背包问题理论基础，416. 分割等和子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
