动态编程: balancer 分区

我想为这个问题实现动态编程算法:输入:非负数的给定排列S

我们想将S分成2个子集S1和S2并最小化| sum(S1)-sum(S2)|,然后以相同的方式划分2个子集,当我们到达具有2或1个元素的子集时停止()我们必须保留S元素的顺序) .

示例:S = {1,2,2,3,4}输出{{{1,2} {2}} {3,4}}

this article的帮助下,这是我的实施:

static String partition(int s[], int db,int fn)
{
    int n = (fn-db) +1;
    String res ="";
    if (n<=2){
        res +="[";
        for(int l =db ;l<=fn;l++) res+=s[l];
        res +="]";
        return res;
    }
    int[][] m= new int [n+1][3];                 /* DP table for values */             
    int[][] d= new int [n+1][3];                 /* DP table for dividers */ 
    int [] p = new int [n+1];                    /* prefix sums array */
    int cost;                               /* test split cost */
    int i,x = 0;                              /* counters */

    p[0] = 0;                               /* construct prefix sums */
    for (i=1; i<=n; i++) 
        p[i]=p[i-1]+s[(db-1)+i];

    for (i=1; i<=n; i++) 
        m[i][1] = p[i];    /* initialize boundaries */
        m[1][2] = s[db];


    for (i=2; i<=n; i++){                    /* evaluate main recurrence */
            m[i][2] = Integer.MAX_VALUE;
            for (x=1; x<=(i-1); x++) {
                cost = Math.max(m[x][1], p[i]-p[x]);
                if (m[i][2] > cost) {
                    m[i][2] = cost;
                    d[i][2] = db+(x-1);
                }
            }
     }
    return res +="["+partition(s,db,d[n][2])+partition(s,d[n][2]+1,fn)+"]";

}

public static void main(String[] args) {
    int []set ={2,1,1,1,5};
    System.out.print(partition(set,0,set.length-1));
}
  • 我的实现是好的还是还有另一个动态编程解决方案whitout递归调用?

  • 我无法计算这个算法的复杂性,我尝试使用主定理T(n)= aT(nb)f(n),但我现在不知道2个递归调用的每个子问题的大小 .

3.如果我们可以改变元素的顺序,我们可以做同样的分区吗?

回答(1)

2 years ago

以这种方式思考:在最坏的情况下,你有一个数组,其中每个索引我包含值2i . 在这种情况下,拆分仅将长度减小一个,这意味着递归深度在n中是线性的 . 在每个级别,您执行O(n)工作,因此总复杂度为O(n2) . 幸运的是,这样的阵列在实践中会非常短暂,因为我们通常不会考虑这么大的数字,因此现实世界的性能通常会更好 . 当权重稍微 balancer 时,您应该具有O(n log n)性能 .

至于第一个问题,我不确定你对“好人”的意思 .

编辑:通过在要分割数组的位置执行二进制搜索,可以提高算法的效率 . 这是可能的,因为必须保留订单 .