dynamic-programming相关内容

将最长的公共子序列减少到最长的子序列

如果最多一个序列具有重复，我们可以将最长公共子序列问题减少为最长增加子序列问题.在此处中说明了减少问题的过程: 假设您具有以下顺序: S1 = {D，B，A，C，E}S2 = {E，Z，X，D，A，Y，C} 然后，创建一个整数序列S3，您必须在其中将S2的每个元素的位置放在S1中(如果该元素在S1中不存在，则忽略该元素).在示例中: S3 = {4，0，2，3}//S2中的Z，X ..
发布时间：2021-05-03 19:05:56 其他开发

重叠子问题和最优子结构之间有什么区别?

我了解这两种方法的目标方法，其中最佳子结构根据输入n计算最佳解决方案，而重叠子问题则针对输入范围(从1到n)的所有解决方案. 针对诸如杆切割问题之类的问题.在这种情况下，当找到最佳切割时，我们是否考虑了每个切割，因此可以将其视为“重叠子问题"，并将其视为自下而上的工作.还是我们考虑给定输入n的最佳切割并自上而下地工作. 因此，尽管它们最终都涉及最优性，但这两种方法之间的确切区别是什么. ..
发布时间：2021-05-03 19:05:53 其他开发

创建对象后更改对象的类型(Python中的类型转换)

在我的项目中，生成类型为 CubicObject 的对象 obj .在运行时，应允许GUI设置将 obj 的类型更改为 Tofu 或 Box (并返回)，具体取决于用户的类型想要做什么以及他认为最能代表该对象的是什么.然后，用户应受益于在相应类中实现的特定算法.我正在寻找这种行为的一个很好的实现.我玩过下面的代码，该代码更改了 __ class __ 属性，但是我确信这是不好的风格. Clas ..
发布时间：2021-05-03 19:05:50 Python

分段线性回归的优化

我正在尝试创建分段线性回归以最小化MSE(最小平方误差)，然后直接使用线性回归.该方法应使用动态编程来计算不同的分段大小和组的组合，以实现整体MSE.我认为算法运行时为O(n²)，我想知道是否有办法将其优化为O(nLogN)? 将numpy导入为np从sklearn.metrics导入mean_squared_error从sklearn导入linear_model将熊猫作为pd导入导入matpl ..
发布时间：2021-05-03 19:05:42 Python

包含全零的子矩阵的数量

有没有一种方法可以找到许多包含全零的矩形子矩阵，其复杂度小于O(n ^ 3)，其中n是给定矩阵的维数? 解决方案 这是解决方案 O(n²log n). 首先，让我们将主要问题转换为以下内容: 对于给定的直方图，找到包含全零的子矩阵的数量. em> 如何转换? 对于每个位置，计算从该位置开始且仅包含零的列的高度. 示例: 10010 0110100111 ..
发布时间：2021-05-03 19:05:35 其他开发

使用动态编程更改硬币

我一直在使用动态编程来解决硬币找零问题.我试图制作一个数组fin []，该数组包含该索引所需的最少硬币数量，然后打印出来.我写了一段代码，我认为它应该给出正确的输出，但是我不知道为什么它没有给出确切的答案.例如:对于输入:4 3 1 2 3 (4是要更改的数量，3是可用硬币的类型数量，1 2 3是硬币值列表)输出应为:0 1 1 1 2(因为我们有1,2,3作为可用硬币，因此需要0硬币更改为0、1 ..
发布时间：2021-05-03 19:05:32 Java开发

查找所有可能在结束和开始时重叠的组合

在帖子找到所有具有非重叠区域的组合(粘贴在下面的代码中)，该函数将获得一组元组，并以递归方式查找具有不重叠值的每个可能的元组集合.在元组列表上 T = [(0.0，2.0)，(0.0，4.0)，(2.5，4.5)，(2.0，5.75)，(2.0，4.0)，(6.0，7.25)] ，例如，我们得到 def nonovl(l，idx，right，ll):如果idx == len(l):如果ll:打 ..
发布时间：2021-05-03 19:05:27 Python

打印背包里麻袋里的物品

假设您是小偷，您入侵了一所房子.在里面发现了以下物品: 一个重3磅，价值50美元的花瓶. 一个重6磅，价值30美元的银块. 这幅画重4磅，价值40美元. 镜子重5磅，价值10美元. 这个10磅大小的背包问题的解决方案是90美元. 通过动态编程制成的表是:- ..
发布时间：2021-05-03 19:05:24 其他开发

我的子集平均问题有DP解决方案吗?

我有一个无法解决的组合问题. 给出一组矢量和一个目标矢量，为每个矢量返回一个标量，以使该组中缩放后的矢量的平均值最接近目标. 编辑:权重w_i在[0，1]范围内.这是一个受约束的优化问题: 最小化d(avg(w_i * x_i)，目标)取决于总和(w_i)-1 = 0 如果我不得不说这个问题，那将是无界子集平均值. 我已经研究了无限制的背包和类似的问题，但是由于数字的 ..
发布时间：2021-04-23 19:10:11 Python

查找总和最小的子数组的索引

给出一个长度为n的数组，该数组带有整数(可以是负数或正数).找到子数组的开始和结束索引，并尽可能减少总和. 解决方案 正如您所指定的，这是关于Kadanes算法的，很容易找到很多有关它的参考. GeeksForGeeks:最小和连续子数组请对该算法进行解释并提供实现几种语言. 基于 python 代码的问题，我对其进行了修改，以返回开始/结束索引而不是总和值.这个想法是保持范围索引和 ..
发布时间：2021-04-16 20:36:14 其他开发

使用动态规划查找三项式系数

我正在尝试使用动态编程在Java中实现一个计算三项式系数的函数.我正在使用公式: 如果n = 0和k = 0，则 T(n，k)= 1如果k ＜-n或k＞ n，则T(n，k)＝ 0.T(n，k)= T(n-1，k-1)+ T(n-1，k)+ T(n-1，k + 1) 我正在使用2D数组存储所有子问题的结果.但是，对于一个特定的 n 和 k 我得到的结果与正确答案相去甚远.这是我对方法的实现 ..
发布时间：2021-04-09 20:07:04 Java开发

计算不同的非空字符串，它们是所有四个字符串的子序列

这是一个 spoj问题，要求您计算不同的非空字符串，全部四个弦的子序列.例如 输入:阿伯阿巴布爸爸阿克巴输出:4这四个序列是"a"，"b"，"aa"和"ab". 我该如何解决这个问题? 解决方案 为了不破坏乐趣，我没有提供完整的答案，只是给您一些想法. 将四个字符串写为 A ， B ， C ， D . 对于非负整数 i ，为 A 的子字符串写 A ，该子字符串是通 ..
发布时间：2021-04-02 20:54:42 其他开发

蛋滴跟踪表

两个蛋的问题: 您将获得2个鸡蛋. 您可以访问100层的建筑物. 鸡蛋可能非常坚硬或非常脆弱，这意味着如果从一楼跌落可能会破裂，甚至从100楼跌落甚至可能不会破裂.两个鸡蛋都是相同的. 您需要弄清楚一栋100层建筑的最高楼层，可以将鸡蛋掉下来而不会破裂. 现在的问题是，您需要滴几滴.在此过程中，您可以打破两个鸡蛋. 我知道使用动态编程解决此问题的方法.我想跟踪解决方案以及最少的 ..
发布时间：2021-04-02 20:53:19 C/C++开发

创建一个时间表，一群人互相交谈-有限制

问题陈述 我想实现以下目标:(例如可以用来为学生组织某种类型的加速活动) 创建时间表，使人们可以一对一地互相交谈，并与小组中的每个成员交谈.但有限制. 输入:人员列表.(例如30人) 限制:有些人不应该互相交谈(例如，彼此认识) 输出:成对列表(分成多个会话)只有一种解决方案是可行的，无需知道所有可能的结果 示例 例如四人一组 约翰 史蒂夫 标记 梅丽 ..
发布时间：2021-04-02 20:52:17 Python