MENU

最佳加法表达式

September 22, 2018 • Read: 3247 • 算法阅读设置

描述

给定n个1到9的数字,要求在数字之间最多添加m个加号(加号两边必须有数字,并且不能有两个或两个以上加号相邻),使得所得到的加法表达式的值最小,并输出该值。

输入

每组数据三行。第一行是整数n,表示有n个数(0<n≤10)
第二行是整数m,表示最多可以使用m个加号
第三行有n个数,每个数的范围都是1到9

样例输入

5
3
1 2 3 4 5

样例输出

51

样例解释

12+34+5=51

解题思路

1.剪枝

首先考虑可以考虑剪枝,总共只有(n-1)个位置可以放加号,并且不能有两个或以上的加号相邻,因此加号最多可以用(n-1)/2个,再引入贪心的策略,加号越多肯定值越小,所以,如果m≤(n-1)/2,那就用m个,如果m>(n-1)/2,那就只用(n-1)/2个

2.dfs

首先声明,所有的下标均从0开始。用dfs(int idx)来枚举所有加号摆放的位置,当idx==m时,就计算产生的值,然后更新最小值。dfs(idx)表示的含义是当前用了idx个加号,所以main函数里调用dfs(0)。然后是dfs函数体里如何枚举的问题,很简单用一层for循环,表示枚举到的位置i,i<n-1

加号放的位置存在mark[]数组里,对于样例12+34+5,对应的mark[]数组值为mark[0]=1,mark[1]=3。num数组的作用主要是存放数字列,例如num0 = 12345,num2=34,方便后面直接用

dfs函数里枚举完加号之后,如何计算也是一个问题,其实也比较简单,定义两个指针i,j,j一直往后遍历,当j遍历到mark[index]时,就将numi的值加在sum里,然后i = j+1,index++,但是这样还有最后一个加号到最后一个数之前的值没加,所以最后还要加上num[mark[index - 1] + 1][n - 1]

3.分析时间复杂度

一个加号就要枚举一遍数字列,m个加号要枚举m次数字列,数字列长度是n,所以时间复杂度是O(mn^2^),暂时没想到什么地方如何用动态规划优化,重复计算的部分比较难想,可能我蒟蒻吧.....

代码

C
#include <stdio.h>
#include <algorithm>
using namespace std;

int n,m;//n和m如题所述
int ans = 0x7fffffff;//最终答案,要找最小值所以初始化为int最大值
int mark[10];//记录放加号的位置,第1个加号的位置在mark[0]
int arr[10];//n个数
int num[10][10];//num[i][j]表示i到j的数字串

void dfs(int idx)//当前用了idx个加号 
{
    if(idx == m)//加号用完了,计算产生式的值 
    {
        int sum = 0;
        int index = 0;
        int i = 0;
        for(int j = 0;j < n;j++)
        {
            if(j == mark[index])
            {
                sum += num[i][j];
                index++;
                i = j + 1;
            }
        }
        sum += num[mark[index - 1] + 1][n - 1];
        ans = min(ans,sum); 
        return;
    }
    for(int i = 0;i < n - 1;i++)
    {
        if(idx == 0)//第一个加号 
        {
            mark[idx] = i;
            dfs(idx + 1);
        }
        else
        {
            if(abs(mark[idx - 1] - i) > 1)//必须满足两个加号之间的距离大于1 
            {
                mark[idx] = i;
                dfs(idx + 1);
            }
        }
    }
} 
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i = 0;i < n;i++) 
    {
        scanf("%d",&arr[i]);
        num[i][i] = arr[i];//i到i产生的数字串就是这个数字自己 
    }
    if(n == 1) //就一个数就直接输出结束 
    {
        printf("%d",arr[0]);
        return 0;
    }
    //预处理num数组 
    for(int i = 0;i < n;i++) 
        for(int j = i + 1;j < n;j++) 
            num[i][j] = num[i][j - 1] * 10 + arr[j];
            
    //剪枝m
    if(n > 2 && m > (n - 1) / 2)
        m = (n - 1) / 2;
        
    dfs(0);//开始搜索 
    printf("%d",ans);
    return 0;
}
Java
import java.util.Scanner;
public class Main {
    static int n, m, ans = 0x7fffffff;
    static int[] mark = new int[10];// 放加号的位置
    static int[] arr = new int[10];
    static int[][] num = new int[10][10];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();// 数字个数
        m = cin.nextInt();// 加号个数
        for (int i = 0; i < n; i++) {
            arr[i] = cin.nextInt();
            num[i][i] = arr[i];
        }
        if (n == 1)//特殊情况,一个数就不用添加加号了,直接输出
            System.out.println(arr[0]);
        else {
            for (int i = 0; i < n; i++)
                for (int j = i + 1; j < n; j++)
                    num[i][j] = num[i][j - 1] * 10 + arr[j];
            for (int i = 0; i < mark.length; i++)
                mark[i] = -1;
            if(n > 2 && m > (n - 1) / 2)//剪枝,有可能根本放不了那么多加号
                m = (n - 1) / 2;
            dfs(0);
            System.out.println(ans);
        }
    }

    static void dfs(int idx) {// 已经用了idx个加号
        if (idx == m) {//加号用完则开始计算产生的值
            int sum = 0;
            int index = 0;
            int i = 0;
            for (int j = 0; j < n; j++) {
                if (j == mark[index]) {
                    sum += num[i][j];
                    index++;
                    i = j + 1;
                }
            }
            sum += num[mark[index - 1] + 1][n - 1];
            ans = Math.min(ans, sum);
            return;
        }
        for (int i = 0; i < n - 1; i++) {// 枚举放加号的位置
            if (idx == 0) {
                mark[idx] = i;
                dfs(idx + 1);
            } else {
                if (Math.abs(mark[idx - 1] - i) > 1) {
                    mark[idx] = i;
                    dfs(idx + 1);
                }
            }
        }
    }
}
Last Modified: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment