标签: dynamic-programming

我有一个与子集求和问题有关的问题,我想知道差异是否更容易,即在合理的时间内可解决.

给定一个值V,一个集合大小L和一个数字序列[1,N] S,S总和的多少个L子集总和小于V？

这与子集求和问题有三种不同:

1. 我关心有多少子集小于给定值,而不是有多少子集相等.
2. 子集大小是固定的.
3. 我关心有多少集合总和小于V,而不仅仅是否存在.

有没有合理有效的算法来解决这个问题？

编辑:显然,这可以使用组合生成算法在O(N选择L)中完成.我真正感兴趣的是聪明的黑客,以显着加快它的速度.

我想矢量化以下MATLAB代码.我认为它必须简单,但我发现它令人困惑.

r = some constant less than m or n
[m,n] = size(C);
S = zeros(m-r,n-r);
for i=1:m-r+1
    for j=1:n-r+1
        S(i,j) = sum(diag(C(i:i+r-1,j:j+r-1)));
    end
end

的代码计算分数,的表小号,对于动态规划算法,从另一个得分表,Ç.
对角线求和是为所有可能的片段(大小为r)生成用于生成C的各个数据片段的分数.

提前感谢您的任何答案!对不起,如果这个显而易见......

注意
内置的conv2比convnfft更快,因为我的眼睛(r)非常小(5 <= r <= 20).convnfft.m表示r应该> 20表示任何利益.

这是另一个动态编程问题(Vazirani ch6)

考虑以下3-PARTITION问题.给定整数a1 ... an,我们想确定是否有可能将{1 ... n}分割为三个不相交的子集I,J,K,使得

sum(I)= sum(J)= sum(K)= 1/3*sum(ALL)

例如,对于输入(1; 2; 3; 4; 4; 5; 8),答案是肯定的,因为存在分区(1; 8),(4; 5),(2; 3; 4).另一方面,对于输入(2; 2; 3; 5),答案是否定的.设计和分析3-PARTITION的动态规划算法,该算法在n和(sum a_i)中以时间多项式运行

我怎么解决这个问题？我知道2分区但仍然无法解决它

我在查找动态编程问题时发现了这一点.您将获得V0 O0 V1 O1 .... Vn-1形式的无限制表达式

我们必须将括号放在最大化整个表达式值的位置.

V是操作数,O是操作符.在问题的第一个版本中,运算符可以是*和+,操作数是正数.问题的第二个版本是完全一般的.

对于第一个版本,我提出了DP解决方案.

解决方案 - A [] =操作数数组B [] - 运算符数组T(A [i,j]) - 表达式T的最大值(A [0,n-1])=最大值i {(T [A [ 0,i])Oi T(A [i + 1,n-1]))}

边界情况是微不足道的(当i = j时).我需要以下帮助 - 分析此算法的运行时间.如果存在更好的一个.

我正在重新阅读Skiena的算法设计手册,以了解自学校以来我忘记的一些东西,我对他对动态编程的描述感到有点困惑.我看着它在维基百科和其他各种网站,并同时说明一切意义,我无法找出具体的问题我自己.目前,我正在从Skiena的书中解决问题3-5.(给定一个n个实数的数组,找到输入的任何连续子向量中的最大总和.)我有一个O(n ^ 2)解决方案,如本答案中所述.但我坚持使用动态编程的O(N)解决方案.我不清楚复发关系应该是什么.

我看到子序列形成一组总和,如下所示:

S = {a,b,c,d}

a    a+b    a+b+c    a+b+c+d
     b      b+c      b+c+d
            c        c+d
                     d

我没有得到的是如何选择哪一个在线性时间内最大.到目前为止,我已经尝试过跟踪最大值的事情,如果当前值为正,则将其添加到总和中.但是当你有更大的序列时,这就成了问题,因为可能有一些负数会减少总和,但是后来的大正数可能会使它恢复到最大值.

我还想起了总面积表.你可以只使用累积和来计算所有的总和:a,a + b,a + b + c,a + b + c + d等等(例如,如果你需要b + c,它只是(a +) b + c) - (a).)但是没有看到O(N)方法来获得它.

任何人都可以向我解释一下这个特定问题的O(N)动态编程解决方案是什么吗？我觉得我几乎得到它,但我错过了一些东西.

我一直在研究本书中的以下问题.

某种字符串处理语言提供了一种原始操作,它将字符串分成两部分.由于此操作涉及复制原始字符串,因此无论剪切的位置如何,对于长度为n的字符串,都需要n个时间单位.现在假设您要将字符串分成许多部分.中断的顺序可能会影响总运行时间.例如,如果你想在3号和10号位置剪切一个20个字符的字符串,那么在第3个位置进行第一次剪切会产生20 + 17 = 37的总成本,而在第10个位置进行第一次剪切会产生更好的成本20+ 10 = 30.

我需要一个动态编程算法,给出m个切割,找到将字符串切割成m + 1个片段的最低成本.

我已经看到各种讨论和代码尝试解决来自interviewstreet.com 的"字符串缩减"问题,但他们都没有通过动态编程来解决它.

在动态编程部分列出,问题描述如下:

给定由a,b和c组成的字符串,我们可以执行以下操作:获取任意两个相邻的不同字符,并将其替换为第三个字符.例如,如果'a'和'c'相邻,则可以用'b'代替.

重复应用此操作可以产生的最小字符串是多少？

可以使用详尽的强力搜索来解决问题,有效地创建所有可能替换的树:

// this is more or less pseudo code from my head
int GetMinLength(string s)
{
    // solve edge cases
    if (s.Length == 1) return 1;
    if (s.Length == 2) return ReduceIfPossible(s);

    // recursive brute force
    int min = s.Length;
    for (int i = 0; i<s.Length-1; i++)
    {
        if (s[i] != s[i+1])
        {
            var next = GetMinLength(
                  s.Substring(0, i) + 
                  Reduce(s[i], s[i + 1]) +
                  s.Substring(i + 2)
                  );

            if …

请考虑以下描述连续integer值范围的界面.

public interface IRange {
    int Minimum { get;}
    int Maximum { get;}

    IRange LargestOverlapRange(IEnumerable<IRange> ranges);
} 

我正在寻找一种有效的算法来找到给定IRange对象列表的最大重叠范围.下图简要概述了这个想法.顶部数字表示integer值,并用最小值和最大值|-----|表示IRange对象.我堆叠了IRange对象,以便解决方案易于可视化.

0123456789  ...                            N
|-------|   |------------|        |-----|
   |---------|    |---|
       |---|             |------------|
               |--------|  |---------------|
                              |----------|

这里,该LargestOverlapRange方法将返回:

                                  |---|

由于该范围总共有4个'重叠'.如果有两个IRange相同数量的重叠,我想返回null.

这是我尝试过的一些简要代码.

public class Range : IRange 
{

    public IRange LargestOverlapRange(IEnumerable<IRange> ranges) {           

        int maxInt = 20000;    

        // Create a histogram of the counts
        int[] histogram = new int[maxInt]; …

如果以随机顺序给出数组,则必须输出转换为循环排序数组所需的最小交换数.

例如,给出的阵列是3 5 4 2 1

所以第一次交换将是5 < - > 4结果:3 4 5 2 1秒交换将是2 < - > 1结果:3 4 5 1 2(最终)

输出:2

我无法理解这个问题背后的逻辑.

添加更多: 只能在相邻元素之间进行交换,数字在1到N之间

我正在研究Rosalind问题Mortal Fibonacci Rabbits,当我使用我的算法编写JavaScript时,网站一直告诉我我的答案是错误的.当我在Python中使用相同的算法时,我会得到一个不同的(和正确的)答案.

只有在结果变大时才会出现不一致.例如,在JavaScript中fibd(90, 19)返回2870048561233730600但在Python中我得到2870048561233731259.

有没有关于JavaScript中的数字给我一个不同的答案或在我的JavaScript代码中犯了一个微妙的错误？

JavaScript解决方案:

function fibd(n, m) {
    // Create an array of length m and set all elements to 0
    var rp = new Array(m);
    rp = rp.map(function(e) { return 0; });
    rp[0] = 1;

    for (var i = 1; i < n; i++) {
        // prepend the sum of all elements from 1 to the end of the array
        rp.splice(0, 0, rp.reduce(function (e, s) { return s …