有依赖的的动态规划问题

题目

在这里插入图片描述
在这里插入图片描述

题型分析

这是比较典型的动态规划的问题。动态规划是什么呢？本质上动态规划是对递归的优化。例如，兔子数列：f(x) = f(x - 1) + f(x -2), 我们知道 f 代表了计算公式，这里解放思想一下，如果 f 替换为数组，将每个 f(x) 的返回值返回，那么是不是就不用计算了，直接返回了，这样就节省了 CPU 递归和计算的时间，提高计算的效率，这样就对递归进行了优化。

public static fb(int input){
   if(input == 1){
      return 1 ;
   }
   if(input == 2){
      return 2 ;
   }
   return fb(input -1) + fb(input - 2);
}

改成动态规划：

public static fb(int input){
   int[] dp = new int[input + 1];
   dp[1] = 1 ;
   dp[2] = 2 ;
   for(int i = 3 ; i <= input ; i++){
     dp[i] = dp[i - 1] + dp[i - 2] ;
   }
   return dp[input] ;
}

斐波那契数列只是一个数列而已。只是我们可以从中总结出一些规律：

  1. 找到初始值。这就是递归的出口。
  2. 然后以初始值为起点，往后继续计算。这代表了各个递归调用。

说完斐波那契数列，我们可以把难度增加。经典的 0-1 背包问题。它题目往往是这样有两个一维数组，第一个代表了容量，第二个代表价值，给定一个 N 正整数值，N 值是背包能装的容量，数组的一个元素代表了一个物品，一个物品只能装一个，问背包能装下的最大价值是多少？
递归的算法：
定义 process(int i , int N , int[][] capacity , int[][] value) , 其中 i 代表 i ~ capacity.length 容量为 N 的情况下，返回最大的价值。
于是可以按两种情况处理。

  1. 不要 i 物品, 那么递归应该 process(i , N ) = process(i + 1 , N)
  2. 要 i 物品，那么递归应该 process(i , N) = value[i] + process(i + 1 , N - capacity[i])
  3. 然后取里面最大的那个。

有了上面的分析，递归可以写为：

    public static int process(int[] weight, int[] value, int startIdx, int bagWeight) {
        if (startIdx == weight.length - 1) {
            return (weight[startIdx] <= bagWeight ? value[startIdx] : 0);
        }
        if (bagWeight == 0) {
            return 0;
        }
        // 不将 startIdx 的物品放入背包
        int v1 = process(weight, value, startIdx + 1, bagWeight);
        int v2 = 0;
        if (bagWeight >= weight[startIdx]) {
            v2 = process(weight, value, startIdx + 1, bagWeight - weight[startIdx])
                    + value[startIdx];
        }

        return Math.max(v2, v1);
    }

同样的如果将 process 看成是数组，那么可以想象：

  1. 可以先计算出 dp[capacity.length -1 ][0 … N] 的初始中，代表的业务含义是当容量从 0 到 N 时的最大价值。
  2. 我们可以看出 i 的值是依赖于 i + 1 的值，所以 dp[capacity.length - 2 ][0 … N] 也可以计算出来，一次类推，数组的所有需要的值都可以计算出来。
  3. 最后返回的是 dp[0][N] 的值就可以了。

于是动态规划的版本如下所示：


    public static int processWithDp(int[] w , int[] v , int bag){
        int[][] dp = new int[w.length+1][bag+1];
        int p1 = 0 ;
        int p2 = 0 ;
        for(int index = w.length - 1 ; index >=0  ; index--){
            for(int rest = 0 ; rest <= bag ; rest++){
                 p1 = dp[index+1][rest];
                 p2 = 0 ;
                 if(rest >= w[index]){
                     p2 = dp[index+1][rest - w[index]] + v[index];
                 }
                 dp[index][rest] =  Math.max(p1 , p2);
            }

        }
        return dp[0][bag] ;
    }

最后说到这个题目，此题是在 0-1 背包的基础上增加了依赖。从题目中，可以知道附件不能离开主件独立存在，所以可以先以主件分组，A1{main , fj1 , fj2 } , A2{main , fj1 , fj2} … 在计算的时候，取下面的最大值。

  1. 不要 i 主件物品， A(i , N) = A(i +1 , N)
  2. 只要 i 主件物品，A(i , N) = A(i + 1 , N - A(i)的价格)
  3. 只要 i 主件、fj1， A(i , N) = A(i + 1 , N - A(i)的价格 - fj1 的价格)
  4. 只要 i 主件、fj2， A(i , N) = A(i + 1 , N - A(i)的价格 - fj2 的价格)
  5. i 主件、fj1、fj2， A(i , N) = A(i + 1 , N - A(i)的价格 - fj1 的价格 - fj2 的价格)

根据这样的理解，编写如下代码:

import java.util.*;  


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int N = 0 ; 
        int m = 0 ;
        List<Product> products = new ArrayList();
        if(in.hasNextInt()) { // 注意 while 处理多个 case
            N = in.nextInt();
            m = in.nextInt();
        }
        for(int a = 1 ; a <= m ; a++){
            products.add(new Product(a ,in.nextInt() , in.nextInt() , in.nextInt()));
        }
        int[][] value = new int[products.size()][3];
        int[][] price = new int[products.size()][3];
        List<Product> main = component(value , price , products);
        System.out.println(maxSatisfiedSocre2(N , main , value , price));
    }
    public static  List<Product> component(int[][] value , int[][] price , List<Product> products){
        List<Product> main = new ArrayList();
        int j = 0 ;
        for(int i = 0 ; i < products.size() ; i++){
            if(products.get(i).q == 0){
                main.add(products.get(i));
                value[j][0] = products.get(i).v;
                price[j][0] = products.get(i).p;
                List<Product> c = getFj(products.get(i).idx , products);
                if(c.size() > 0){
                    value[j][1] = c.get(0).p;
                    price[j][1] = c.get(0).v;
                    if(c.size() > 1 ){
                        value[j][2] = c.get(1).p;
                        price[j][2] = c.get(1).v;
                    }
                }

                j++;
            }
        }
        return main ;
    }
    public static List<Product> getFj(int id , List<Product> products){
        List<Product> rs = new ArrayList<Product>();
        for(int i = 0 ; i < products.size() ; i++){
            if(id == products.get(i).q){
                rs.add(products.get(i));
            }
        }
        return rs ;
    }
    public static class Product{
        public int idx ;
        public int v ;
        public int p ;
        public int q ;
        public Product(int idx ,int v , int p , int q){
            this.idx = idx ;
            this.v = v ;
            this.p = p ;
            this.q = q ;
        }
    }
    // 递归版本，此解法会超时
    public static int maxSatisfiedSocre(int N ,List<Product> products , int[][] value , int[][] price){
        if(N == 0 || null == products || products.size() == 0) return 0 ;
        return process(0 , N , products , value , price);
    }
    // 动态递归的解法
    public static int maxSatisfiedSocre2(int N ,List<Product> products , int[][] value , int[][] price){
        if(N == 0 || null == products || products.size() == 0) return 0 ;
        int[][] dp = new int[products.size()][N+1];
        int p1 = -1 ;
        int p2 = -1 ;
        int p3 = -1 ;
        int p4 = -1 ;
        int idx = products.size()-1 ;
        // int j = N ;
        for(int j = N ; j >= products.get(idx).v ; j-- ){
            p1 = -1 ;
            p2 = -1 ;
            p3 = -1 ;
            p4 = -1 ;
            if( j >= products.get(idx).v){
                p1 = products.get(idx).v*products.get(idx).p ;
                // dp[idx][j - products.get(idx).v] = p1 ;
            }

            if(j >= products.get(idx).v + price[idx][1]){
                p2 = products.get(idx).v*products.get(idx).p + value[idx][1]*price[idx][1] ;
                // dp[idx][j - products.get(idx).v - price[idx][1]] = p2 ;              
            }
        
            if(j >= products.get(idx).v + price[idx][2]){
                p3 = products.get(idx).v*products.get(idx).p + value[idx][2]*price[idx][2] ;
                // dp[idx][j - products.get(idx).v - price[idx][2]] = p3 ;              
            }
                
            if(j >= products.get(idx).v + price[idx][1] + price[idx][2]){
                p4 = products.get(idx).v*products.get(idx).p + value[idx][1]*price[idx][1] + value[idx][2]*price[idx][2] ;
                // dp[idx][j - products.get(idx).v - price[idx][1] - price[idx][2]] = p4 ;
            }
            dp[idx][j] = Math.max(Math.max(p1 , p2) , Math.max(p3 , p4));
        }
        int p5 = -1 ;
        for(int i = products.size() - 2 ; i>=0  ; i--){
            for(int j = N ; j > 0 ; j--){
                p1 = -1 ;
                p2 = -1 ;
                p3 = -1 ;
                p4 = -1 ;
                p5 = -1 ;
                if( j >= products.get(i).v ){
                    p1 = products.get(i).v*products.get(i).p + dp[i+1][j - products.get(i).v];
                    // dp[i][j - products.get(i).v] = p1 ;
                }
                if(j >= products.get(i).v + price[i][1]){
                    p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + dp[i+1][j - products.get(i).v - price[i][1]];
                    // dp[i][j - products.get(i).v - price[i][1]] = p2;
                }
                if(j >= products.get(i).v + price[i][2]){
                    p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] + dp[i+1][j - products.get(i).v - price[i][2]];
                    // dp[i][j - products.get(i).v - price[i][2]] = p3 ;                 

                }
                if(j >= products.get(i).v + price[i][1] + price[i][2]){
                    p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] + dp[i+1][j - products.get(i).v - price[i][1] - price[i][2]];
                    // dp[i][j - products.get(i).v - price[i][1] - price[i][2] ] = p4 ;  
                }
                
                // 不要 i
                p5 = dp[i+1][j];
                dp[i][j] = Math.max(Math.max(p1 , p2) , Math.max(Math.max(p3 , p4) , p5));
            }
        }
        return dp[0][N];
    }
    // 递归版本的实际实现。
    public static int process(int i , int N , List<Product> products , int[][] value , int[][] price){
        if(i + 1 == products.size()){
            int p1 = -1 ;
            int p2 = -1 ;
            int p3 = -1 ;
            int p4 = -1 ;
            if( N >= products.get(i).v){
               p1 = products.get(i).v*products.get(i).p ;
            }
            if(N >= products.get(i).v + price[i][1]){
                p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] ;
            }
            if(N >= products.get(i).v + price[i][2]){
                p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] ;
            }
            if(N >= products.get(i).v + price[i][1] + price[i][2]){
                p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] ;
            }
            return Math.max(Math.max(p1 , p2) , Math.max(p3 , p4));
        }
        int p1 = -1 ;
        int p2 = -1 ;
        int p3 = -1 ;
        int p4 = -1 ;
        // 只要 i 的作为主键
        int next = process(i+1 , N - products.get(i).v , products , value , price);
        if(-1 == next){
            next = 0 ;
        }
        if( N >= products.get(i).v ){
            p1 = products.get(i).v*products.get(i).p + next ;
        }
        if(N >= products.get(i).v + price[i][1]){
            next = process(i+1 , N - products.get(i).v - price[i][1] , products , value , price);
            if(-1 == next){
                next = 0 ;
            }
            p2 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + next ;
        }
        if(N >= products.get(i).v + price[i][2]){
            next = process(i+1 , N - products.get(i).v - price[i][2] , products , value , price);
            if(-1 == next){
                next = 0 ;
            }
            p3 = products.get(i).v*products.get(i).p + value[i][2]*price[i][2] + next;
        }
        if(N >= products.get(i).v + price[i][1] + price[i][2]){
            next = process(i+1 , N - products.get(i).v - price[i][1] - price[i][2] , products , value , price);
            if(-1 == next){
                next = 0 ;
            }
            p4 = products.get(i).v*products.get(i).p + value[i][1]*price[i][1] + value[i][2]*price[i][2] + next;
        }
        // 不要 i
        int p5 = process(i+1 , N , products , value , price);
        return Math.max(Math.max(p1 , p2) , Math.max(p5 , Math.max(p3 , p4)));
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/546859.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue实现前端打印效果

vue实现前端打印效果

如图效果所示&#xff08;以下演示代码&#xff09; <template><div><el-button v-print"printObj" type"primary" plain click"handle">{{ text }}</el-button><div style"display: none"><div id…
阅读更多...
基于Springboot+Vue的Java项目-在线视频教育平台系统(附演示视频+源码+LW)

基于Springboot+Vue的Java项目-在线视频教育平台系统(附演示视频+源码+LW)

大家好&#xff01;我是程序员一帆&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &am…
阅读更多...
鸿蒙OS开发指导：【应用包签名工具】

鸿蒙OS开发指导：【应用包签名工具】

编译构建 该工具基于Maven3编译构建&#xff0c;请确认环境已安装配置Maven3环境&#xff0c;并且版本正确 mvn -version下载代码&#xff0c;命令行打开文件目录至developtools_hapsigner/hapsigntool&#xff0c;执行命令进行编译打包 mvn package编译后得到二进制文件&…
阅读更多...
[开发日志系列]PDF图书在线系统20240415

[开发日志系列]PDF图书在线系统20240415

20240414 Step1: 创建基础vueelment项目框架[耗时: 1h25min(8:45-10:10)] 检查node > 升级至最新 (考虑到时间问题,没有使用npm命令行执行,而是觉得删除重新下载最新版本) > > 配置vue3框架 ​ 取名:Online PDF Book System 遇到的报错: 第一报错: npm ERR! …
阅读更多...
halcon 3.2标定相机

halcon 3.2标定相机

参考《solution_guide_iii_c_3d_vision.pdf》 3.2.2.2 Which Distortion Model to Use 选用何种畸变模型 对于面阵相机&#xff0c;halcon中两种畸变模型&#xff1a;The division model and the polynomial model&#xff08;差分模型和多项式模型&#xff09;&#xff0c;前…
阅读更多...
使用 Scrapy 爬取豆瓣电影 Top250

使用 Scrapy 爬取豆瓣电影 Top250

一、Scrapy框架 1. 介绍 在当今数字化的时代&#xff0c;数据是一种宝贵的资源&#xff0c;而网络爬虫&#xff08;Web Scraping&#xff09;则是获取网络数据的重要工具之一。而在 Python 生态系统中&#xff0c;Scrapy 框架作为一种高效、灵活的网络爬虫框架&#xff0c;为…
阅读更多...
MLOps

MLOps

参考&#xff1a; 什么是MLOps&#xff1f;与DevOps有何异同&#xff1f;有什么价值&#xff1f;https://baijiahao.baidu.com/s?id1765071998288593530&wfrspider&forpcMLOps简介_AI开发平台ModelArts_WorkflowMLOps(Machine Learning Operation)是机器学习&#xf…
阅读更多...
更优性能与性价比，从自建 ELK 迁移到 SLS 开始

更优性能与性价比，从自建 ELK 迁移到 SLS 开始

作者&#xff1a;荆磊 背景 ELK (Elasticsearch、Logstash、Kibana) 是当下开源领域主流的日志解决方案&#xff0c;在可观测场景下有比较广泛的应用。 随着数字化进程加速&#xff0c;机器数据日志增加&#xff0c;自建 ELK 在面临大规模数据、查询性能等方面有较多问题和挑…
阅读更多...
【自动驾驶】贝叶斯算法在机器学习中的应用研究

【自动驾驶】贝叶斯算法在机器学习中的应用研究

目录 第一章&#xff1a;引言 1.1 贝叶斯算法在机器学习中的重要性 1.2 研究背景 1.3 研究目的 1.4 论文结构 第二章&#xff1a;贝叶斯算法概述 2.1 贝叶斯定理 2.2 贝叶斯算法分类 第三章&#xff1a;贝叶斯算法在机器学习中的应用 3.1 贝叶斯分类器 3.2 贝叶斯回…
阅读更多...
【软考】UML中的图之用例图

【软考】UML中的图之用例图

目录 1. 说明2. 建模2.1 说明2.2 语境建模2.3 需求建模 3. 图示4. 组成部分 1. 说明 1.用例图&#xff08;Use Case Diagram&#xff09;。2.展现了一组用例、参与者&#xff08;Actor&#xff09;以及它们之间的关系。3.用例图通常包括以下的内容&#xff1a;用例、参与者、用…
阅读更多...
linux 自定义快捷指令(docker

linux 自定义快捷指令(docker

vi /root/.bashrc alias disdocker images alias dpsdocker ps --format "table {{.ID}}\t{{.Image}}\t{{.Ports}}\t{{.Status}}\t{{.Names}}" 保存退出后使用sourece /root/.bashrc 让其立即生效 sourece /root/.bashrc
阅读更多...
python 判断变量是数字型还是字符型

python 判断变量是数字型还是字符型

python如何判断数据类型&#xff1f;方法如下&#xff1a; 使用type()函数&#xff1a; import types type(x) is types.IntType # 判断是否int 类型 type(x) is types.StringType #是否string类型可以不用记住types.StringType&#xff0c;即&#xff1a; import types type(…
阅读更多...
Adobe Premiere 2015 下载地址及安装教程

Adobe Premiere 2015 下载地址及安装教程

Premiere是一款专业的视频编辑软件&#xff0c;由Adobe Systems开发。它为用户提供了丰富的视频编辑工具和创意效果&#xff0c;可用于电影、电视节目、广告和其他多媒体项目的制作。 Premiere具有直观的用户界面和强大的功能&#xff0c;使得编辑和处理视频变得简单而高效。它…
阅读更多...
【leetcode面试经典150题】51. 用最少数量的箭引爆气球（C++）

【leetcode面试经典150题】51. 用最少数量的箭引爆气球（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…
阅读更多...
2024蓝桥A组E题

2024蓝桥A组E题

成绩统计 问题描述格式输入格式输出样例输入样例输出评测用例规模与约定解析参考程序难度等级 问题描述 题目有问题方差定义那加平方&#xff08;vi-v&#xff09; 格式输入 输入的第一行包含三个正整数n,k,T &#xff0c;相邻整数之间使用一个空格分隔。 第二行包含n个正整数…
阅读更多...
FPGA - 仲裁器的设计实现

FPGA - 仲裁器的设计实现

一&#xff0c;为什么做仲裁 在多主单从的设计中&#xff0c;当多个源端同时发起传输请求时&#xff0c;这个时候就需要仲裁器来根据优先级来判断响应哪一个源端&#xff0c;向其传输数据。比如&#xff1a;以太网仲裁&#xff0c;DDR仲裁&#xff0c;光纤传图仲裁..... 二&a…
阅读更多...
线程安全---synchronized

线程安全---synchronized

直接上代码 private static int a 0;public static void main(String[] args) throws InterruptedException {Thread t1 new Thread(() -> {for(int i 0; i < 50000; i){a;}});Thread t2 new Thread(() -> {for(int i 0; i < 50000; i){a;}});t1.start();t2.s…
阅读更多...
Module Federation微前端应用拆分后 - request请求优化、私有化request｜分发拦截器

Module Federation微前端应用拆分后 - request请求优化、私有化request｜分发拦截器

1. 背景及目的 1.1 需求背景 随着应用的拆分&#xff0c;目前子应用有12个&#xff0c;这些子应用都使用的是同一个request实例。 前端支持后端切流&#xff0c;增加多个拦截器用于灰度 经手动梳理&#xff1a; 目前所有应用中有26个在使用的拦截器&#xff0c; 其中用于灰…
阅读更多...
hive了解系列一

hive了解系列一

“ 随着智能手机的普及&#xff0c;互联网时代红利的爆发&#xff0c;用户数量和产生的数据也越发庞大。为了解决这个问题&#xff0c;提高数据的使用价值。 Hadoop生态系统就被广泛得到应用。 在早期&#xff0c;Hadoop生态系统就是为处理如此大数据集而产生的一个合乎成本效益…
阅读更多...
【JAVA基础篇教学】第十四篇：Java中设计模式

【JAVA基础篇教学】第十四篇：Java中设计模式

博主打算从0-1讲解下java基础教学&#xff0c;今天教学第十四篇&#xff1a;Java中设计模式。 设计模式是解决软件设计中常见问题的可重复利用的解决方案。在 Java 中&#xff0c;常见的设计模式包括单例模式、工厂模式、观察者模式等。目前在基础教学篇中只展示常见的几种模…
阅读更多...
最新文章

Copyright @ 2022~2023