代码学习记录34---动态规划

这篇具有很好参考价值的文章主要介绍了代码学习记录34---动态规划。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

随想录日记part34

t i m e : time: time 2024.04.02



主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及两个方面:
背包问题和分割等和子集。

  • 01背包问题
  • 416. 分割等和子集


动态规划五部曲:
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组

Topic101背包问题

题目:
小明是一位科学家,他需要参加一场重要的国际科学大会,以展示自己的最新研究成果。他需要带一些研究材料,但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等,它们各自占据不同的空间,并且具有不同的价值。 小明的行李空间为 N,问小明应该如何抉择,才能携带最大价值的研究材料,每种研究材料只能选择一次,并且只有选与不选两种选择,不能进行切割。
输入描述:
第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。
第二行包含 M 个正整数,代表每种研究材料的所占空间。
第三行包含 M 个正整数,代表每种研究材料的价值。

输入:
6   1 2   2   3   1   5   2 2   3   1   5   4   3 6\ 1\\ 2\ 2\ 3\ 1\ 5\ 2\\ 2\ 3\ 1\ 5\ 4\ 3 6 12 2 3 1 5 22 3 1 5 4 3
输出: 5 5 5

思路:

【1】.二维dp数组01背包
1.dp含义:dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
2.确定递推公式
有两个方向推出来dp[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]);

代码如下:

mport java.util.*;
class Main{
    public static void main(String[] agrs){
        Scanner sc = new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int[] weights=new int[m];
        int[] values=new int[m];
        for(int i=0;i<m;i++){
            weights[i]=sc.nextInt();
        }
        for(int i=0;i<m;i++){
            values[i]=sc.nextInt();
        }
        //dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少
        int[][] dp=new int[m][n+1];
        //初始化
        for(int i=0;i<m;i++){
            dp[i][0]=0;
        }
        for(int i=weights[0];i<=n;i++){
            dp[0][i]=values[0];
        }
        //状态转换
        for(int i=1;i<m;i++){
            for(int j=0;j<=n;j++){
                if(j<weights[i])dp[i][j]=dp[i-1][j];
                else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j - weights[i]]+values[i]);
            }
        }
        System.out.println(dp[m-1][n]);
    }
}

【2】.滚动数组01背包
倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
举一个例子:物品0的重量weight[0] = 1,价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了,意味着物品0,被放入了两次,所以不能正序遍历。
为什么倒序遍历,就可以保证物品只放入一次呢?
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 (dp数组已经都初始化为0)
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
代码如下:

import java.util.*;
class Main{
    public static void main(String[] agrs){
        Scanner sc = new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int[] weights=new int[m];
        int[] values=new int[m];
        for(int i=0;i<m;i++){
            weights[i]=sc.nextInt();
        }
        for(int i=0;i<m;i++){
            values[i]=sc.nextInt();
        }
        //dp[i]表示放进容量为j的背包,价值总和最大是多少
        int[] dp=new int[n+1];
        //初始化
        //状态转换
        for(int i=0;i<m;i++){
            for(int j=n;j>=weights[i];j--){
                dp[j]=Math.max(dp[j],dp[j-weights[i]]+values[i]);
            }
        }
        System.out.println(dp[n]);
    }
}


Topic2分割等和子集

题目:

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

输入: n u m s = [ 1 , 5 , 11 , 5 ] nums = [1,5,11,5] nums=[1,5,11,5]
输出: t r u e true true

思路:

按照上面的五个步骤给出下面的代码,在注释中给出具体的思路:
递推我们理解一下:
整体代码如下:

class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        //dp[j]表示背包总容量(所能装的总重量)是j,放进物品后,背的最大重量为dp[j]
        int[] dp=new int[10001];
        if(sum%2==1) return false;
        sum=sum/2;
        for(int i=0;i<nums.length;i++){
            for(int j=sum;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[sum]==sum) return true;
        else return false;
    }
}

时间复杂度 O ( n 2 ) O(n^2) O(n2)
空间复杂度 O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-846210.html



到了这里,关于代码学习记录34---动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)

    背包问题是一种经典的组合优化问题,通常有两个版本:0-1背包问题和无限背包问题。 0-1背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品只能选择放入

    2024年02月09日
    浏览(48)
  • 算法记录 | 48 动态规划

    思路: 1.确定dp数组(dp table)以及下标的含义: dp[i]:前 i 间房屋所能偷窃到的最高金额。 2.确定递推公式: dp[i] = max(dp[i - 2] + nums[i-1], dp[i - 1]) i间房屋的最后一个房子是nums[i−1]。 如果房屋数大于等于 2 间,则偷窃第 i−1 间房屋的时候,就有两种状态: 偷窃第 i−1 间房屋

    2024年02月05日
    浏览(37)
  • 算法记录 | Day53 动态规划

    思路: 本题和动态规划:718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了,但要有相对顺序,即:“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。 1.确定dp数组(dp table)以及下标的含义 dp[i][j] :长度为[0, i - 1]的字符串text1与长度为[0,

    2024年02月03日
    浏览(49)
  • 算法记录 | Day46 动态规划

    思路: 1.确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词 。 2.确定递推公式 如果 s[0: j] 可以拆分为单词(即 dp[j] == True ),并且字符串 s[j: i] 出现在字典中,则 dp[i] = True 。 如果 s[0: j] 不可以拆分为单词(即

    2024年02月02日
    浏览(39)
  • 算法记录 | Day38 动态规划

    对于动态规划问题,将拆解为如下五步曲 确定dp数组(dp table)以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 思路: 确定dp数组(dp table)以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i] 确定递推公式:状态转移方程 dp[i] = dp

    2023年04月22日
    浏览(44)
  • 算法记录 | Day55 动态规划

    思路: 1.确定dp数组(dp table)以及下标的含义: dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为 dp[i][j] 。 2.确定递推公式: if (s[i - 1] == t[j - 1]) t中找到了一个字符在s中也出现了, dp[i][j] = dp[i - 1][j - 1] + 1 if (s[i - 1] != t[j - 1]) 相当于t要

    2024年02月03日
    浏览(49)
  • 算法记录 | Day45 动态规划

    改为:一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢? 1阶,2阶,… m阶就是物品,楼顶就是背包。 每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。 问跳到楼顶有几种方法其实就是问装满背包有几种方法。 此时大家

    2024年02月11日
    浏览(33)
  • Leetcode题解-算法-动态规划(python版)

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种,1、先走 1 级台阶,再走 n-1 级台阶;2、先走 2 级台阶,再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(51)
  • Day 42算法记录| 动态规划 08

    单词就是物品,字符串s就是背包 1.dp[0]背包啥也不要用装,true。 2. for循环,顺序很重要,所以先背包再物品 如果求组合数就是外层for循环遍历物品,内层for遍历背包 。 如果求排列数就是外层for遍历背包,内层for循环遍历物品 。 3.递归: 要么装包或者不装 添加链接描述 把

    2024年02月15日
    浏览(31)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包