首页 文章

动态编程： balancer 分区

提问于
浏览 次
2

我想为这个问题实现动态编程算法：输入：非负数的给定排列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.如果我们可以改变元素的顺序，我们可以做同样的分区吗？

java algorithm

1 回答

  • 0

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

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

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

    回复于

相关问题