我遇到了使用耐心排序来获取最长递增子序列（LIS）长度的解决方案。http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf，这里 - http://en.wikipedia.org/wiki/Patience_sorting。

遵循贪婪策略实际上可以正确给出长度的证明有两部分 -

1. 证明桩数至少为等于LIS的长度。
2. 证明使用贪心策略的桩数至多等于LIS。

因此，凭借 1) 和 2)，该解正确给出了 LIS 的长度。

我得到了 1) 的解释，但我无法直观地认识到 2) 部分。有人可以使用不同的例子来说服我这确实是真的吗？或者，您甚至也可以使用不同的证明技术。

可能重复:
在重叠间隔序列中查找最大总和的算法

我正在解决以下修改后的活动调度(贪婪方法)问题:

给定n个活动的集合S和开始时间,Si和fi,完成第i个活动的时间.同样给予重量wi,Foo为进行第i次活动所获得的成本.

问题是选择最大化foo收益的活动.我们必须返回foo可以赚取的最高成本.假设Foo一次只能处理一个活动.

注意::

这类似于经典的Activity选择问题 ,这里唯一的区别是,对于每个活动,我们都给出了一个成本wi.这里的目标太不同了 - 在这个问题中,我们必须找到最大化foo总收入的一组活动,而不是找到相互兼容的活动的最大规模集.

例

Total activities N=4
Si fi wi
0 1 4000
2 5 100
1 4 3000
4 5 2500

Max earning=9500 (Answer)

如何修改经典贪婪活动选择算法,以解决此问题.我应该用什么逻辑来解决上述问题？

我做了一个tic tac toe AI鉴于每个板状态,我的AI将返回一个确切的位置移动.(即使移动同样正确,每次选择相同的移动,也不会选择随机移动)

我还创建了一个函数,循环使用AI进行的所有可能的播放

因此它是一个递归函数,让AI为给定的板移动,然后让另一个游戏进行所有可能的移动,并在每个可能的移动中使用新板自己调用递归函数.

我这样做是因为人工智能首先出现,而当另一个首先出现时...并将它们加在一起.我最终获得了418次可能的胜利和115种可能的关系,以及0次可能的失败.

但现在我的问题是,如何最大限度地赢得胜利？我需要将这个统计数据与某些东西进行比较,但我无法弄清楚要将它与之进行比较.

我做了一个tic tac toe AI鉴于每个板状态,我的AI将返回一个确切的位置移动.我还创建了一个函数,循环使用AI进行的所有可能的播放

因此它是一个递归函数,让AI为给定的板移动,然后让另一个游戏进行所有可能的移动,并在每个可能的移动中使用新板自己调用递归函数.

我这样做是因为人工智能首先出现,而当另一个首先出现时...并将它们加在一起.我最终获得了418次可能的胜利和115种可能的关系,以及0次可能的失败.

但现在我的问题是,如何最大限度地赢得胜利？我需要将这个统计数据与某些东西进行比较,但我无法弄清楚要将它与之进行比较.

如果使用贪婪方法可以解决优化问题,那么它的所有最优解都必须始终包含第一个选择(即贪婪的选择)吗？

在页面的最后,有人试图解释贪婪,不情愿和占有欲量词如何工作:http://docs.oracle.com/javase/tutorial/essential/regex/quant.html

然而,我尝试了一个例子,我似乎并没有完全理解它.

我会直接粘贴我的结果:

Enter your regex: .*+foo
Enter input string to search: xfooxxxxxxfoo
No match found.

Enter your regex: (.*)+foo
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

为什么第一个reg.exp.找不到匹配,第二个呢？这两个reg.exp之间的确切区别是什么？

我正在尝试了解贪婪算法调度问题的工作原理。

因此，由于我无法理解Greedy算法调度问题，因此我已经阅读并进行了一段时间的搜索。

我们有n个工作要安排在单个资源上。作业（i）具有请求的开始时间s（i）和结束时间f（i）。

我们选择了一些贪婪的想法...

• 以s的升序接受（“最早的开始时间”）
• 以f-s（“最短工作时间”）的升序接受
• 以递增的顺序接受冲突（“最小冲突”）
• 以f的升序接受（“最早完成时间”）

书中说最后一个，以f的递增顺序接受总是会给出最佳解决方案。

但是，它没有提及为什么总是提供最佳解决方案，以及为什么其他3个都不提供最佳解决方案。

他们提供的数字说明了为什么其他三个将无法提供最佳解决方案，但我无法理解其含义。

由于信誉不佳，我无法发布任何图像，所以我将尝试绘制它。

？| --- | | --- | | --- |
| ------------------------- |
s低估解的增加阶

| ----------- | | ----------- |
??? | ----- |
fs被低估的解的增加阶

| ---- |？| ---- |？| ---- | ？| ---- |

？| ----- |？| ----- |？| ----- |

？| ----- | ???? | ----- |

？| ----- | ???? | ----- |

冲突数量的增加顺序。被低估的解决方案

这是它的外观，我不明白为什么这是每种情况的反例。

如果有人能解释每个贪婪的想法为何行不通的话，它将非常有帮助。

谢谢。

我正在处理这个问题,这与改变硬币问题很相似.

我需要实现一个简单的计算器,它可以用当前数字x执行以下三个操作:乘以x乘以2,将x乘以3,或者将x加1.

目标给出正整数n,找到从数字1开始获得数字n所需的最小操作数.

我做了一个贪婪的方法,它显示不正确的结果

import sys

def optimal_sequence(n):
    sequence = []
    while n >= 1:
        sequence.append(n)
        if n % 3 == 0:
            n = n // 3
        elif n % 2 == 0:
            n = n // 2
        else:
            n = n - 1
    return reversed(sequence)

input = sys.stdin.read()
n = int(input)
sequence = list(optimal_sequence(n))
print(len(sequence) - 1)
for x in sequence:
    print(x)

例如:

Input: 10
Output: 
4
1 2 4 5 10

4个步骤.但正确的是3个步骤:

Output: 
3
1 3 9 10 …

该代码的输出错误，n=2非常慢。

我如何才能使此代码更有效地找到尽可能多的正独立求幂？

任务 -将给定的正整数n表示为尽可能多的成对截然不同的正整数之和。

输出：第一个包含一个整数。k第二行包含一个k正的，不同的正加和，总计为n。

Sample Input:

8

Output:

3

1 2 5

n=int(input())
p=[]
i=1
while(i<=n):
      if (n-i) not in p:
          p.append(i)
      n-=i
      i+=1
print(len(p))
print(*p)

以下是两种不同的解决方案,用于查找"产品小于K的子阵列数",一个具有运行时O(n),另一个具有O(n ^ 2).然而,O(n ^ 2)完成执行的速度比具有线性运行时复杂度的速度快1倍(1s vs 4s).有人可以解释为什么会这样吗,拜托？

具有O(n)运行时的解决方案1:

static long countProductsLessThanK(int[] numbers, int k)
{
    if (k <= 1) { return 0; }

    int prod = 1;
    int count = 0;

    for (int right = 0, left = 0; right < numbers.length; right++) {
        prod *= numbers[right];

        while (prod >= k)
            prod /= numbers[left++];

        count += (right-left)+1;
    }

    return count;
}

具有O(n ^ 2)运行时的解决方案2:

static long countProductsLessThanK(int[] numbers, int k) {
    long count = 0;

    for (int i = 0; …