是的,在SO上有很多这样的问题.我看到遗传算法是最常见的答案.
但是,我担心GA的这些特征
我希望该程序能够被用户轻松推向相互冲突的标准和不可能的解决方案 .
因此,我想要一种方法
有100000个尽可能详尽的时间表.
我四处搜索,发现像模拟退火这样的元启发式算法是一个很好的选择.那么动态编程算法呢？
对于这样的数据集,蛮力方法是否合适？
什么是符合标准的好算法？
language-agnostic algorithm artificial-intelligence dynamic-programming genetic-algorithm
在最近由“AmDocs”组织的比赛中，我遇到了以下问题：（问题的基本思想）
你是一个固定大小的矩阵 12x12。您将获得六个长度为 6、5、5、4、3、2 的线段。矩阵有空的空间和填充的空间。您必须返回 "Yes" 或 "No" ，无论所有 6 条线段是否可以同时适合矩阵。线条只能水平或垂直放置。
应该使用什么算法来解决这个问题？包装 ？背包？
我正在阅读Knapsack Problem(无界),正如我理解DP中的经典之作.
虽然我认为我在阅读时理解了解决方案,但我不清楚如何将其转换为实际代码.
例如,在以下重复"公式"中:
M(j) = MAX {M(j-1), MAX i = 1 to n (M(j - Si) + Vi) } for j >=1
我不知道如何将其转换为代码,因为我不清楚内部MAX应该在那里还是应该只是代替:
M(j) = MAX {M(j-1), M(j - Si) + Vi } for j >=1
有什么帮助找出公式并编码吗？
我只知道通过分支定界，可以减少获取解决方案的过程，但这仅对具有解决方案空间树的问题有所帮助。
给定数量NI需要找到从1到N具有至少一个素数(2,3,5或7)的数字的计数.
现在N可以达到10 ^ 18.什么是解决这个问题的最佳方法.
示例:设N = 100,答案为64.
请帮忙解决这个问题.
代码:这是主要功能.但显然不是很好的方法
long long int n;
cin>>n;
long long int count=0;
for(int i=1;i<=n;i++){
long long temp=i;
while(temp>0){
int rem=temp%10;
if(rem==2 || rem==3 ||rem==5 || rem==7){
count++;
break;
}
temp=temp/10;
}
}
我需要将一个数组分成k个或更少的子部分,以最小化每个部分的最大总和.
例如,数组包含元素: 5,10,21,20
如果k=2,阵列可以划分为2个子阵列:{5,10,21}和{20}.我们必须返回子阵列的最大总和(36在上面的例子中).
何时k>=4,答案将只是数组中最大的元素.
此外,无法更改数组元素的选择顺序,因此我们不能只对数组进行排序并继续.
您将获得一个字符串,例如"acdfdcqqc",我们需要创建一个算法来查找最大的回文子字符串"cdfdc".通过创建一个大小为2n的数组来设计O(n ^ 2)算法很容易,并且每次计算最大回文的长度,其中心点为:
a - c - d - f - d - c - q - q - c
1 0 1 0 1 0 5 0 1 0 1 0 1 4 1 0 1
对于2n个可能的起点中的每一个,我在两个方向上移动,找到从该位置开始的最大回文的长度.因此,对于我在大多数O(n)操作中执行的2n个操作中的每一个,因此O(n ^ 2)时间复杂度.
我知道它可以使用发烧友算法在线性时间内完成:https://en.wikipedia.org/wiki/Longest_palindromic_substring.
但假设我们处理的字符串是从自然英文文本中提取的.如果我们在英文文本中随机选择一个位置,那么我们可能期望找到的预期对称性非常低.我甚至会说,预期的对称性在每一方都不到一个字符.因此,我可以说我的算法正在进行2n次预期的恒定时间操作,使得算法平均值为O(n)吗？
这里最大和子集是k个子集之一，它给出最大和，例如：arr = [10,5,3,7]和k =将arr划分为k个子集的2种可能方式是{10，[5,3,7]} ，{{10,5]，[3,7}，{[10,5,3]，7}和{[10,5]，[3,7}是最佳选择。编辑：它等效于 https://www.codechef.com/DI15R080/problems/MINMAXTF
我理解为什么DP比简单的递归更有效.
但是,我知道DP是使用memoization技术的递归.
对于Fibonacci,像这样:
int DP[10000]; //initalized by 0
int f(int num){
if (DP[num] != 0)
return DP[num];
DP[num] = f(num -1) + f(num - 2);
return DP[num];
}
我总是以这种递归方式使用DP,并且它在ACM等算法问题上运行良好.
最近,我知道大多数人都不会以这种方式使用DP.
他们像这样使用DP:
int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[n+1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 …我正在努力解决这个问题。现在，我能够获得递归解决方案：
如果DP[n]给出以字符串的第n个字符结尾的漂亮的子字符串（在问题中定义）的数量，则要查找DP[n+1]，我们从第（n + 1）个字符向后扫描输入字符串，直到找到第i个字符，使得子字符串从第i个字符开始到第（n + 1）个字符结束都是很漂亮的。如果找不到这样的人，DP[n+1] = 0。
如果这样的字符串被找到，那么，DP[n+1] = 1 + DP[i-1]。
麻烦的是，这种解决方案使一个测试用例超时。我怀疑是向后扫描部分存在问题。我的解决方案的总体时间复杂度似乎为O(N^2)。输入数据的大小似乎表明问题需要O(NlogN)解决。