转载请注明出处：優 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
为例。
第一步，先切下一个
“
第二步，再切下一个
“
第三步，再切下一个
“
第四步，再切下一个
“
第五步，再切下
“
(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
}
