POJ1416-Shredding Company

来源:互联网 时间:1970-01-01

转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1304031265

 

题目翻译:

公司现在要发明一种新的碎纸机,要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值。比如,target的值是50,而纸条上的数字是12346,应该把数字切成四部分,分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。(比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50,而12, 34, 6也不可以,因为它们的和超过50了。碎纸还有以下三个要求:

1、如果target的值等于纸条上的值,则不能切。
2、如果没有办法把纸条上的数字切成小于target,则输出error。如target是1而纸条上的数字是123,则无论你如何切得到的和都比1大。
3、如果有超过一种以上的切法得到最佳值,则输出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的不完全搜索树

省略号为未列出的结点

 1 //Memory Time
2 //4160K 157MS
3
4 #include<iostream>
5 #include<cmath>
6 #include<string>
7 using namespace std;
8
9 int getlen(int n) //得到n的位长度
10 {
11 if(n<10)
12 return 1;
13 else if(n<100)
14 return 2;
15 else if(n<1000)
16 return 3;
17 else if(n<10000)
18 return 4;
19 else if(n<100000)
20 return 5;
21 else
22 return 6;
23 }
24
25 int getvalue(char* s,int i) //得到数字字符串s前i位字符(数字)组成的int值
26 {
27 int k=i;
28 int sum=0;
29 while(k)
30 {
31 k--;
32 sum+=(s[k]-'0')*(int)pow(10.0,(double)(i-k-1));
33 }
34 return sum;
35 }
36
37 int gethead(int n,int i) //得到由n的前i位数字构成的int
38 {
39 int len=getlen(n);
40 if(len<=i)
41 return n;
42 return n/(int)pow(10.0,(double)(len-i));
43 }
44
45 int gettail(int n,int i) //得到由n的后i位数字构成的int
46 {
47 return n%(int)pow(10.0,(double)i);
48 }
49
50 int aim; //目标数
51
52 int result; //最优划分的和
53 int path; //最优划分的划分方式
54
55 int sum; //某种划分的和
56 int p; //某种划分方式
57
58 int vist[1000000]; //记录每个sum出现的次数
59 //999999是当n=999999时的最大和值
60
61 void DFS(char* s,int len)
62 {
63 if(len==0)
64 {
65 vist[sum]++;
66 if(sum>result && sum<=aim)
67 {
68 result=sum;
69 path=p;
70 }
71 return;
72 }
73
74 for(int i=1;i<=len;i++)
75 {
76 int a=getvalue(s,i); //n的前i位字符转变为数字留下,计入部分和
77 sum+=a; //部分和
78 if(sum>aim) //剪枝,部分和已经大于aim,无需继续往下搜索
79 {
80 sum-=a;
81 continue;
82 }
83 p=p*10+i; //记录划分方式
84
85 char b[7]; //构造n的后i位字符序列,继续递归
86 int j=0;
87 for(int k=i;k<len;k++)
88 b[j++]=s[k];
89 b[j]='/0';
90
91 DFS(b,len-i);
92
93 sum-=a; //回溯
94 p/=10;
95 }
96 return;
97 }
98
99 int main(void)
100 {
101 while(true)
102 {
103 /*Input*/
104
105 char s[7]; //打印纸上的数字
106 cin>>aim>>s;
107
108 int len=strlen(s);
109 int n=getvalue(s,len); //构造s的数字序列n
110
111 if(!aim && !n)
112 break;
113
114 if(aim==n) //目标值与打印纸上的数字一致
115 {
116 cout<<aim<<' '<<n<<endl;
117 continue;
118 }
119
120 int num=n; //temporary
121 int k=0; //n的各位数字之和
122 while(num)
123 {
124 k+=num%10; //逐位划分是 和最小的划分方式
125 num/=10;
126 }
127 if(k>aim) //最小和也大于aim,则所有划分都大于aim
128 {
129 cout<<"error"<<endl;
130 continue;
131 }
132
133 /*Initial*/
134
135 result=-1;
136 sum=0;
137 path=0;
138 p=0;
139 memset(vist,0,sizeof(vist));
140
141 /*DFS*/
142
143 DFS(s,len);
144
145 /*Output*/
146
147 if(vist[result]>1) //最优解多于一个
148 cout<<"rejected"<<endl;
149 else if(vist[result]==1) //有唯一最优解
150 {
151 cout<<result<<' ';
152
153 int L=getlen(path); //输出划分的方式
154 for(int i=1;i<=L;i++)
155 {
156 int k=gethead(path,1); //取path的第一位k,k的值等于n的第一段划分位数,即从n的第1位到第k位
157 cout<<gethead(n,k)<<' ';
158 n=gettail(n,len-=k);
159 path=gettail(path,L-i);
160 }
161 cout<<endl;
162 }
163 }
164 return 0;
165 }
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b我的新浪微博:http://weibo.com/lyy289065406我的腾讯微博:http://t.qq.com/liao5422我的QQ空间:http://user.qzone.qq.com/289065406我的百度空间:http://hi.baidu.com/you289065406/home我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


相关阅读:
Top