代码随想录-算法训练营day41(动态规划04:01背包,01背包滚动数组,分割等和子集)
第九章 动态规划part04● 01背包问题，你该了解这些！
● 01背包问题，你该了解这些！ 滚动数组
● 416. 分割等和子集 正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。 如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。 背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。 详细布置 01背包问题 二维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6 01背包问题 一维
https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
视频讲解：https://www.bilibili.com/video/BV1BU4y177kY 416. 分割等和子集
本题是 01背包的应用类题目
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE
day41
01背包
方法一:二维数组
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n; i++){weight[i] = sc.nextInt();}for(int i = 0; i<n; i++){value[i] = sc.nextInt();}//dp[i][j]表示0~i的物品放在容量j的背包的最大价值int[][] dp = new int[n][bagweight + 1];//初始化,dp[i][j]来自dp[i - 1][j]和dp[i - 1][j - weight[i]],所以初始化第1行和第1列for(int j = weight[0] ; j <= bagweight; j++){dp[0][j] = value[0];}for(int i = 1; i < n; i++){//对于二维数组,先遍历物品还是背包容量都可以,因为都来自正上方和左上方for(int j = 1; j <= bagweight; j++){if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);//注意可以更新压缩成一维数组,dp[i][j]都是由dp[i-1][j或者j-weight[i]]得来的}}System.out.println(dp[n - 1][bagweight]);}}
方法二:一维数组
//把[i]这个维度压缩了,滚动数组的时候从后往前遍历,因为每个数据都是需要上一行正上的数据和上一行左边的数据,在同一行操作的时候如果优先改了左边的数据,右边的数据更新会被影响import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int bagweight = sc.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i = 0; i < n; i++){weight[i] = sc.nextInt();}for(int i = 0; i<n; i++){value[i] = sc.nextInt();}int[] dp = new int[bagweight + 1];for(int j = weight[0] ; j <= bagweight; j++){dp[j] = value[0];}for(int i = 1; i < n; i++){for(int j = bagweight; j >= weight[i]; j--){//if(j < weight[i]) dp[j] = dp[j];//判断多余了//else
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bagweight]);}}
分割等和子集
//相当于weight[i]和value[i]相同的bagweight = sum/2的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）//不用遍历完i,出现满足题意的装满的背包直接返回就行//为什么一定会在dp[target]处出现满足题意的背包,dp[target]有可能不正好是target,而是更大或者更小跳过正好是target的情况吗?//不可能,一个空间就是一个价值,target装满了最大就是target,只有可能是装满/不装满这两种情况,所以就是求最大价值的背包if(dp[target] == target)return true;}return dp[target] == target;}}
感谢大佬分享:
代码随想录-算法训练营day41【动态规划04：01背包问题-滚动数组、分割等和子集】_分隔等和子集 [1,5,11,5] 背包 滚动数组-CSDN博客