大多数时候,令人困惑的事实是,是否要进行详尽的搜索(动态编程或反向跟踪或蛮力)来解决问题或采用贪婪的方法.
我不是在谈论使用贪婪来确定最佳解决方案,我说的是使用贪婪算法来找到"解决方案".我试图找到一些标准的方法,我可以验证问题是否可以通过贪婪的方法解决.像Optimal子结构一样,用于动态编程的记忆.并没有任何具体问题.
有没有我可以做的归纳证明来决定贪婪方法是否总能产生最佳解决方案？
以下是问题https://www.hackerrank.com/challenges/equal的链接
我读了它的社论,无法理解.如果你没有对hackerrank做任何说明,那么肯定你不会看到它的社论,所以这里有一些编辑.
这相当于说,christy可以将一个同事的巧克力带走1,2或5,同时保持其他人的巧克力不受影响.
让我们考虑减少同事的巧克力作为一种手术.为了减少操作次数,我们应该尝试使每个同事的巧克力数量等于组中的最小值(分钟).我们必须通过(A [i] - min)减少第i个人A [i]的巧克力数量.设这个值为x.
This can be done in k operations.
k = x/5 +(x%5)/2 + (x%5)%2
从这里我无法理解
设f(min)是对所有同事进行的操作的总和,以将每个巧克力减少到最小值.但是,有时f(min)可能并不总是给出正确的答案.它也可以是一种情况
f(min) > f(min-1)
f(min) < f(min-5)
因为f(min-5)需要N次操作多于f(min),其中N是同事的数量.因此,如果
A = {min,min-1,min-2,min-3,min-4}
then f(A) <= f(min) < f(min-5)
谁能帮助我理解为什么这有必要检查f(min),f(min-1),...,f(min-4)
我最近遇到过这个问题.假设x轴上有n个点,x [0],x [1] .. x [n-1].让与这些点中的每一个相关联的权重为w [0],w [1] ... w [n-1].从0到n-1之间的任何点开始,目标是覆盖所有点,使得w [i]*d [i]的总和最小化,其中d [i]是到达第i个点所覆盖的距离.起点.
示例:
假设点数为:1 5 10 20 40
假设权重为:1 2 10 50 13
如果我选择从点10开始并选择移动到点20然后到5然后再到40然后最终到1,那么加权和将变为10*0 + 50*(10)+ 2*(10 + 15)+ 13*(10 + 15 + 35)+ 1*(10 + 15 + 35 + 39).
我试图通过贪婪的方法解决它,从具有最大相关权重的点开始并移动到第二个最大权重点,依此类推.但算法不起作用.有人可以指点一下解决这个问题必须采取的方法吗？
我遇到了这个看起来非常有趣的问题.我们想要观看所有电影,但它们仅在以下时间显示:
movieA : 15
movieB : 14, 15, 17
movieC : 15, 17
movieD : 15, 20
我们可以看到15分,B分14分,C分17分和D分数20分,所以可以全部观看.请注意,你不能在15看C,不可行.
你猜到的问题是我们是否可以全部看到它们.
显然,我们可以通过回溯来解决它,尝试所有可能性.有更好的方法吗？我有一个想法,首先从具有最少可用时间的电影开始,这样我们可以更快地找到解决方案,如果有解决方案,最坏的情况时间复杂性仍然是相同的.
那个问题有更好的算法吗？
PS正如@gen所问,我忘了指出每部电影都是1小时,所以如果你在14:00看一部电影,你就不会错过15点的电影.谢谢你的询问.
我不擅长以编程方式实现启发式搜索算法/提到的Dijkstra算法/ A*搜索算法.然而,在解决我的一篇文章中提到的问题(矩阵操作:逻辑没有获得更高阶NXN矩阵数据的正确答案)时,我发现了解决问题的方法中的一个缺陷.问题陈述如下.
问题陈述
有一个NxN矩阵,分为N*N个单元.每个单元格都有一个预定义值.这将作为输入.迭代必须发生K次,这也是在测试输入中给出的.我们必须确保在每次迭代时选择行/列的最佳/最小值.最终输出是每次迭代结束时保存的最佳值的累积和.
步骤1.总结单个行和列,找到行和列的最小总和(它可以是行或列,只需要最小行或列)
步骤2.分别存储上面找到的总和
第3步.增加min的元素.总和行或列.由1
从1到Kth值重复步骤1,2,3
在每次迭代时添加总和(在步骤2中指定)
输出是在第K次迭代上获得的总和.
样本数据
2, 4 //input data N,K
[1, 3] //matrix' first row
[2, 4] //matrix' second row
输出数据 22
我的守则
void matrixManipulation() throws IOException {
int N = Reader.nextInt();
int[][] matrix = new int[N][N];
int K = Reader.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = Reader.nextInt();
}
}
int[] row = new int[N];
int[] …最近我一直在研究一些贪婪的算法问题.我对局部最优而感到困惑.如您所知,贪婪算法由局部最优选择组成.但是,结合局部最优决策并不一定意味着全局最优,对吧？
以改变为例:使用最少数量的硬币制作15¢,如果我们有10¢,5¢和1¢硬币,那么你可以用一个10¢和一个5¢来实现.但是如果加上12美分硬币,贪婪算法就会失败,因为(1×12¢+ 3×1¢)使用的硬币多于(1×10¢+ 1×5¢).
考虑一些经典的贪婪算法,例如Huffman,Dijkstra.在我看来,这些算法是成功的,因为它们没有退化情况,这意味着局部最优步骤的组合总是等于全局最优.我理解对吗？
如果我的理解是正确的,有没有一种通用的方法来检查贪婪算法是否是最优的？
我碰到了这个问题,我不确定我的解决方案是否是最佳的.
给定N加权(Wi)和可能重叠的间隔(表示会议时间表),找到进行所有会议所需的会议室的最小数量"&".
|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
|------8-----| |----------10-----------|
|--------6-------|
对于上述时间表,我们需要两个10和10个容量的会议室.( 我对么 ？ )
如果我们有一个容量大于需要的会议室使用它,如果没有符合标准的会议室,建立新房间或增加现有房间,请从一个房间,并从左侧穿过间隔.新的能力.
例:
10点开始 - {10}
8点开始 - {10,8}
10月底结束 - {10-free,8}
6点开始 - {10,8}
结束8 - {10,8-free}
10的开头= {10,8 + = 2}或{10,10}
等等.....
这基本上是贪心的..
我试图解决一个面试问题:
给定n*n的矩阵.每个单元格包含0,1,-1.0表示没有钻石,但有一条路径.1表示在该位置处存在菱形,其中路径-1表示路径被阻挡.现在你从0,0开始到达最后一个单元格,然后返回到0,0收集最大的钻石数量.在前往最后一个单元格时,您只能向右和向下移动.返回时,您只能向左和向上移动.
我已经解决了这个问题,但我不确定这是最佳解决方案.我在做什么
有关正确性的任何建议吗？我写了代码,如果需要,我会分享.
因此，一个热心的搜索是你拿即使更好的解决方案是初步的解决方案只是在路上...
什么是相反的期限为跃跃欲试的搜索？我所有的谷歌搜索结果都让我参考了 Paul Revere 的骑行。在这些混乱和不确定的时代，确实是一个令人欣慰的想法，但并不是真的……有用。
有这样的说法吗？
我在编程竞赛中遇到了这个问题:
我们给出一个由n个元素组成的数组.在每次迭代中,您可以选择任何两个元素一个我和一个Ĵ并更换一个我有一个我和一个Ĵ.&是按位AND运算符.找到使所有数组元素为零所需的最小AND操作数.
假设存在给定输入的解决方案.这个问题的最佳解决方案是什么？
greedy ×10
algorithm ×9
correctness ×1
dynamic ×1
global ×1
heuristics ×1
intervals ×1
java ×1
matrix ×1
scheduling ×1
sorting ×1