加载中...

POJ 1416 - Shredding Company


问题描述

公司现在要发明一种新的碎纸机,要求新的碎纸机能够把纸条上的数字切成最接近而不超过 target 值。

比如,target 的值是 50,而纸条上的数字是 12346,应该把数字切成四部分,分别是 1、2、34、6。因为这样所得到的和 43 = (1 + 2 + 34 + 6) 是所有可能中最接近而不超过 50 的(比如 1, 23, 4, 和 6 就不可以,因为它们的和不如 43 接近 50,而 12, 34, 6 也不可以,因为它们的和超过 50 了)。

碎纸还有以下三个要求:

  • 如果 target 的值等于纸条上的值,则不能切。
  • 如果没有办法把纸条上的数字切成小于 target,则输出 error。如 target 是 1 而纸条上的数字是 123,则无论你如何切得到的和都比 1 大。
  • 如果有超过一种以上的切法得到最佳值,则输出 rejected。如 target 为 15,纸条上的数字是 111,则有以下两种切法 11、1 或者 1、11.

你的任务是编写程序对数字进行划分以达到最佳值。

解题思路

DFS 深搜

  1. 比如一个 6 位数 n,切成为 6 个数的话,这 6 个数的和如果大于目标数 aim 则不用再搜索了,因为这肯定是所有划分中和最小的,而最小都比目标数大,自然就没有合要求的答案了.
  2. 如何切分,假如以 50 和 12346 为例:
    • 第一步,先切下一个 “1”,然后递归去切 “2346”;
    • 第二步,再切下一个 “12”,然后递归去切 “346”;
    • 第三步,再切下一个 “123”,然后递归去切 “46”;
    • 第四步,再切下一个 “1234” 然后递归去切 “6”
    • 第五步,再切下 “12346”。
  3. 切下来的 前面的数字串部分 则加入到划分的和,剩下的部分继续递归,直到剩下的数字串长度为 0。 可以用一个 int 记录划分方式 (int p), 如上例的输入为 50 和 12346 时,其结果为 43 = (1 + 2 + 34 + 6),那么 p=1121,代表把 12346 划分为 4 部分,第一部分为第 1 位,第二部分为第 2 位,第三部分为第 3、4 位,第四部分为第 5 位
  4. 注意在搜索时,必须把 n 的 剩余数字部分 转化为字符串再搜索,不然若 剩余的数字开头第一位为 0 时,会导致出错。
  5. 剪枝方法:在搜索时若发现部分和 大于(不能等于)aim 时,则可结束搜索。
  6. error 的判定要在搜索前进行,rejected(多个最优解)的判定要在搜索后判定。
  7. 关于出现相同最优解的标记,每出每种划分的 sum 每出现一次标记 +1,要使标记为 O(1),只需把 vist 数组开得足够大。N 最多为 6 位数,因此 Maxsum=999999

简单的附上一个关于例 50 和 12346 的不完全搜索树

省略号为未列出的结点

AC 源码

//Memory Time
//4160K 157MS 

#include<iostream>
#include<cmath>
#include<string>
using namespace std;

int getlen(int n)  //得到n的位长度
{
    if(n<10)
        return 1;
    else if(n<100)
        return 2;
    else if(n<1000)
        return 3;
    else if(n<10000)
        return 4;
    else if(n<100000)
        return 5;
    else
        return 6;
}

int getvalue(char* s,int i)  //得到数字字符串s前i位字符(数字)组成的int值
{
    int k=i;
    int sum=0;
    while(k)
    {
        k--;
        sum+=(s[k]-'0')*(int)pow(10.0,(double)(i-k-1));
    }
    return sum;
}

int gethead(int n,int i)  //得到由n的前i位数字构成的int
{
    int len=getlen(n);
    if(len<=i)
        return n;
    return n/(int)pow(10.0,(double)(len-i));
}

int gettail(int n,int i)  //得到由n的后i位数字构成的int
{
    return n%(int)pow(10.0,(double)i);
}

int aim;  //目标数

int result;  //最优划分的和
int path;  //最优划分的划分方式

int sum;   //某种划分的和
int p;  //某种划分方式

int vist[1000000];  //记录每个sum出现的次数
                     //999999是当n=999999时的最大和值

void DFS(char* s,int len)
{
    if(len==0)
    {
        vist[sum]++;
        if(sum>result && sum<=aim)
        {
            result=sum;
            path=p;
        }
        return;
    }

    for(int i=1;i<=len;i++)
    {
        int a=getvalue(s,i);  //n的前i位字符转变为数字留下,计入部分和
        sum+=a;  //部分和
        if(sum>aim)  //剪枝,部分和已经大于aim,无需继续往下搜索
        {
            sum-=a;
            continue;
        }
        p=p*10+i;  //记录划分方式

        char b[7];  //构造n的后i位字符序列,继续递归
        int j=0;
        for(int k=i;k<len;k++)
            b[j++]=s[k];
        b[j]='\0';

        DFS(b,len-i);

        sum-=a;  //回溯
        p/=10;
    }
    return;
}

int main(void)
{
    while(true)
    {
        /*Input*/

        char s[7];  //打印纸上的数字
        cin>>aim>>s;

        int len=strlen(s);
        int n=getvalue(s,len);  //构造s的数字序列n

        if(!aim && !n)
            break;

        if(aim==n)      //目标值与打印纸上的数字一致
        {
            cout<<aim<<' '<<n<<endl;
            continue;
        }

        int num=n; //temporary
        int k=0; //n的各位数字之和
        while(num)
        {
            k+=num%10;   //逐位划分是 和最小的划分方式
            num/=10;
        }
        if(k>aim) //最小和也大于aim,则所有划分都大于aim
        {
            cout<<"error"<<endl;
            continue;
        }

        /*Initial*/

        result=-1;
        sum=0;
        path=0;
        p=0;
        memset(vist,0,sizeof(vist));

        /*DFS*/

        DFS(s,len);

        /*Output*/

        if(vist[result]>1)  //最优解多于一个
            cout<<"rejected"<<endl;
        else if(vist[result]==1)  //有唯一最优解
        {
            cout<<result<<' ';

            int L=getlen(path);  //输出划分的方式
            for(int i=1;i<=L;i++)
            {
                int k=gethead(path,1);   //取path的第一位k,k的值等于n的第一段划分位数,即从n的第1位到第k位
                cout<<gethead(n,k)<<' ';
                n=gettail(n,len-=k);
                path=gettail(path,L-i);
            }
            cout<<endl;
        }
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录