首页 > 试题广场 >

米兔分绳子

[编程题]米兔分绳子

热度指数：107 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

随着小米同学搬进小米科技园，米兔们也搬进来啦。
为了给米兔准备新家，行政小姐姐和米兔们玩了一个游戏：
有一个装满了绳子的箱子，绳子有长有短，由米兔们将这些绳子分成两份，之后行政小姐姐负责将这两份绳子拼接成两条长绳，这两条长绳将作为矩形的两条直角边用来规划米兔新家的大小。
注意：绳子不能裁断，不能丢弃。
假设拼接时绳子没有长度损失，设计一段程序计算一下这箱绳子能规划出的最大面积是多少。
一共有 $\mathit n$ 条绳子，用整型数组 $\mathit array$ 表示绳子的长短

示例1

输入

3,[3,4,5]

输出

说明

3,4一组，5一组

备注:

算法知识视频讲解

神丶乐

 public static int maxarea (int n, int[] array) {
        // write code here
        int sum=0;
        for(int i=0;i<n;i++){
            sum=sum+array[i];
        }
        int[][] area=new int[n+1][sum+1];
        for(int i=0;i<n+1;i++){
            Arrays.fill(area[i],0);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=sum/2+1;j++){
                if(j>array[i-1]){
                    int c=(area[i-1][j-array[i-1]]+array[i-1])*(sum-(area[i-1][j-array[i-1]]+array[i-1]));
                    int d=area[i-1][j]*(sum-area[i-1][j]);
                    if((area[i-1][j-array[i-1]]+array[i-1])*(sum-(area[i-1][j-array[i-1]]+array[i-1]))>area[i-1][j]*(sum-area[i-1][j])){
                        area[i][j]=area[i-1][j-array[i-1]]+array[i-1];
                    }else {
                        area[i][j]=area[i-1][j];
                    }
                }else{
                    area[i][j]=area[i-1][j];
                }
            }
        }
        return area[n][sum/2+1]*(sum-area[n][sum/2+1]);
    }

01背包问题的变形，需要取一半的长度当作每个数组的长度，我的这个没用一维数组那种空间优化版本

发表于 2022-01-24 09:56:45 回复(0)