我一直在研究使用Haskell的抽象国际象棋算法(试图扩展我对不同范式的理解),并且我遇到了一个我一直在思考几周的挑战.
这是问题所在:
给定一个板(由整数列表表示;每个整数代表一个后续点值),维度为nxn,确定提供最多点的路径.如果最佳路径存在平局,则返回其中任何一个.
以下是具体内容:
A = [[5,4,3,1],[10,2,1,0],[0,1,2,0],[2,3,4,20]]
其呈现为:
R1: 5 4 3 1, R2: 10 2 1 0, R3: 0 1 2 0, R4: 2 3 4 20.
规则是:
你可以从最上面的任何地方开始
您可以一次移动一个方格,可以是直下,左下(对角线)或右下(对角线).
输出必须是整数元组.
第一个元素是表示列与行的列表,第二个元素是总点数.例如.对于上面的板,最好的解决方案是从左上角(5)行进并沿对角线行进剩余的步骤(直到20点方形).这将导致元组([1,2,3,4], 29).
记住,这一切都在Haskell中,因此它是一个功能范式的递归问题.起初,我正在考虑使用贪婪算法,即选择r1中的最高值,并通过比较接下来的3种可能性进行递归; 选择3中的最高值.然而,垮台是贪婪算法无法在下一行之前看到潜力.
我该怎么做？我不是在寻找代码本身,因为我喜欢自己解决问题.但是,非常感谢伪代码或一些算法指导!
我觉得Kadane的算法是最大子数组问题的真正动态规划解决方案的修改版本。为什么我会这么觉得？我觉得是因为计算最大子数组的方法可以采用：
for(i=0;i<N;i++)
{
DP[i][A[i]]=true;
for(j= -ve maximum ;j<= +ve maximum ;j++)
if(DP[i-1][j])
DP[i][j+A[i]]=true;
}
递归是如果可以用一个以 i-1 个元素结尾的子数组来形成j，我可以使用第 i 个元素形成j+A[i]并且也可以通过在第 i 个位置开始一个子阵列来单独形成A[i]并且最后我们可以在这个 DP 数组中搜索标记为 true 的最大 j！
注意：DP[i][j]表示是否可以使用以 i 结尾的子数组来生成 j！在这里我假设 j 也可以是负数。！现在可以很容易地推导出 sum+ 一个负数 < sum 。这意味着添加任何负指数无助于获得更好的总和，这就是我们可以放弃它们的原因！Morover 我们关心直到i-1th 位置的最大 j并将它与i th 元素连接起来，这让我觉得这是一种贪婪的选择（只是因为最大值 + 元素给了我一个最大值）。
注意：我现在还没有研究过贪婪算法，但我知道什么是贪婪的选择！
编辑：有人说我的算法没有任何意义，所以我试图发布我的代码以使自己清楚。我没有把 j 当作 -ve，因为它们没有成果。我重复我的状态被定义为是否可以使用以 i 结尾的子数组来生成 j。
#include<bits/stdc++.h>
using namespace std;
int DP[101][101];
int main()
{
int i,j,ans=INT_MIN;
int …你好，我刚刚开始学习贪心算法，我首先研究了经典的硬币兑换问题。我可以理解算法中的贪婪（即，选择局部最优解以获得全局最优解），因为我选择硬币的最高值，使得 sum +{所选硬币的值}<=total value。然后我开始解决一些网站上的一些贪心算法问题。我可以解决大部分问题，但无法弄清楚贪婪到底在哪里在问题中应用的具体位置。我针对这些问题编写了我能想到的唯一解决方案并得到了接受。社论也展示了解决问题的相同方法，但我无法理解贪婪范式在算法中的应用。
贪心算法是解决特定范围问题的唯一方法吗？或者它们是解决问题的一种更有效的方法？
您能否给我使用和不应用贪婪范式的同一问题的伪代码？
我正在当地社区大学学习Java课程的数据结构和算法,而且我完全坚持目前的家庭作业.问题如下......
编写一个程序,将各种权重的对象打包到容器中.每个容器最多可容纳10磅.
该程序使用一种贪婪的算法,将一个对象放入它适合的第一个bin中.
我不是要求为我完成作业,我只是希望能指出正确的方向.我的程序非常接近工作,但我无法让它100%正常运行.我能够让第一个容器保持适当的重量,但之后我的其余容器每个容器只能容纳一个重量值.这是我到目前为止所拥有的......
import java.util.ArrayList;
public class Lab20 {
public static void main(String[] args) {
final java.util.Scanner input = new java.util.Scanner(System.in);
System.out.print("Enter the number of objects: ");
double[] items = new double[input.nextInt()];
System.out.print("Enter the weight of the objects: ");
for (int i = 0; i < items.length; i++) {
items[i] = input.nextDouble();
}
ArrayList<Bin> containers = firstFit(items);
//Display results
for (int i = 0; i < containers.size(); i++) {
System.out.println("Container " + (i + 1)
+ " contains objects …我有以下问题：
解决背包0-1问题（不是分数） 假设每个物体都有重量
w1或w2（只有两个重量）。容量=W，算法必须运行在O(nlogn)上。
我尝试解决，贪心算法不行，动态规划算法是O(n*W)。
谁能给我提示。谢谢。
algorithm knapsack-problem dynamic-programming greedy time-complexity
例如，与
k=10
A=[2,1,3]
B=[7,8,9]
答案是肯定的，因为您可以重新排列元素
A=[1,2,3]
B=[9,8,7]
A[i]+B[i] >= 10 = k那么对于来说这是真的i=0,1,2。我的算法是贪心的，就像
int k = parameters[1];
int[] A = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int?[] B = Array.ConvertAll(Console.ReadLine().Split(' '), Extensions.ToNullableInt);
Array.Sort(B);
for(int j = 0; j < A.Length; ++j)
{
bool found = false;
for(int m = 0; j < B.Length && !found; ++j)
{
if(B[m] == null)
continue;
if((A[j] + B[m]) >= k)
{
found = true;
B[m] = null;
}
}
if(!found)
{
Console.WriteLine("NO");
return;
}
} …如果 Kruskal 算法贪婪，为什么它会找到最小生成树？最小生成树不是全局优化问题吗？贪婪的意义不是在于您有可能找不到最佳解决方案吗？那么 Kruskal 如何能够在贪婪的同时找到最小生成树呢？
根据Zeckendorf定理，每个正整数都可以以唯一的方式写为非连续的不同斐波那契数之和。可以使用贪婪算法轻松找到这种分解，该算法主要包括减去适合并迭代的最大斐波那契数，例如：
20 = 13 + 7 = 13 + 5 + 2
但是，该定理还暗示，任何整数（也<= 0）作为唯一的，非连续的negaFibonacci数之和具有唯一分解，即序列
0、1，-1、2，-3、5，-8，...
或F _（-n）=（-1）^（n + 1）F_n。一些例子：
-4 = - 3 - 1
4 = 5 + 1
11 = 13 - 3 + 1
是否有已知的简便算法以这种方式分解给定整数？
我正在阅读有关Binary search 的不同材料，我不清楚它是一个贪婪的二进制（在我看来不是），或者，它可以是具有某些特定实现的贪婪算法吗？
如果它可以是贪婪的，它如何有意义？如果通过选择局部最优获得全局最优，不重新考虑以前的选择，就不能保证二分查找的正确结果。
输入
\n\n\n(1)汽车满油箱可行驶的最大距离：L公里；
\n(2) 一个整数数组，[0, x1, x2, \xe2\x80\xa6, xn, xn+1]，每个整数代表一个位置到源点A的距离。第一个整数为0，即A和A之间的距离。第二个距离x1，表示第一个加油站和A之间的距离。A和B（目的地）之间有n个加油站。xn是最后一个加油站到A的距离，xn+1是B到A的距离。
\n(3)n，为加油站数量。
\n
输出
\n\n\n从 A 到 B 的最少补充次数
\n
代码
\nnumRefills = 0\ncurrentPosition = 0\n\nwhile(currentPosition <= n){\n lastPosition = currentPosition\n\n while(currentPosition <= n && x[currentPosition + 1] \xe2\x80\x93 x[lastPosition] <= L) {\n currentPosition++;\n }\n\n if (currentPosition == lastPosition) return IMPOSSIBLE; \n if (currentPosition <= n) numRefills ++;\n}\n\nreturn numRefills\n我的疑问是：
\n\n\n
- 为什么上面代码的时间复杂度是O(n)？至少因为嵌套的 while 循环，它不应该是 O(n^2) 吗？
\n- 如何证明“在最远的距离加气”是安全的举动？
\n- 除了使用 …