轉(zhuǎn)載請注明出處：優(yōu) YoU? http://user.qzone.qq.com/289065406/blog/1304031265
?
題目翻譯
:
公司現(xiàn)在要發(fā)明一種新的碎紙機(jī)，要求新的碎紙機(jī)能夠把紙條上的數(shù)字切成最接近而不超過 target 值。比如， target 的值是 50 ，而紙條上的數(shù)字是 12346 ，應(yīng)該把數(shù)字切成四部分，分別是 1 、 2 、 34 、 6 。因?yàn)檫@樣所得到的和 43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超過 50 的。（比如 1, 23, 4, 和 6 就不可以 , 因?yàn)樗鼈兊暮筒蝗? 43 接近 50 ，而 12, 34, 6 也不可以，因?yàn)樗鼈兊暮统^ 50 了。碎紙還有以下三個(gè)要求：
1
、如果
target
的值等于紙條上的值，則不能切。
2
、如果沒有辦法把紙條上的數(shù)字切成小于
target
，則輸出
error
。如
target
是
1
而紙條上的數(shù)字是
123
，則無論你如何切得到的和都比
1
大。
3
、如果有超過一種以上的切法得到最佳值，則輸出
rejected
。如
target
為
15
，紙條上的數(shù)字是
111
，則有以下兩種切法
11
、
1
或者
1
、
11.
你的任務(wù)是編寫程序?qū)?shù)字進(jìn)行劃分以達(dá)到最佳值。
解題思路：
用
DFS
深搜
(1)
比如一個(gè)
6
位數(shù)
n
，切成為
6
個(gè)數(shù)的話，這
6
個(gè)數(shù)的和如果大于目標(biāo)數(shù)
aim
則不用再搜索了，因?yàn)檫@肯定是所有劃分中和最小的，而最小都比目標(biāo)數(shù)大，自然就沒有合要求的答案了
.
(2)
如何切分，假如以
50
?
12346
為例。
第一步，先切下一個(gè)
“
第二步，再切下一個(gè)
“
第三步，再切下一個(gè)
“
第四步，再切下一個(gè)
“
第五步，再切下
“
(3) 切下來的 前面的數(shù)字串部分 則加入到劃分的和，剩下的部分繼續(xù)遞歸，直到剩下的數(shù)字串長度為 0 。 可以用一個(gè) int 記錄劃分方式 (int p) ， 如上例的輸入為 50 ? 12346 時(shí)，其結(jié)果為 43 ? 1 ? 2 ? 34 ? 6 ，那么 p=1121 ，代表把 12346 劃分為 4 部分，第一部分為第 1 位，第二部分為第 2 位，第三部分為第 3 、 4 位，第四部分為第 5 位
(4) 注意在搜索時(shí)，必須把 n 的 剩余數(shù)字部分 轉(zhuǎn)化為字符串再搜索，不然若 剩余的數(shù)字開頭第一位為 0 時(shí)，會導(dǎo)致出錯(cuò)。
(5) 剪枝方法：在搜索時(shí)若發(fā)現(xiàn)部分和 大于（不能等于） aim 時(shí)，則可結(jié)束搜索。
(6)error 的判定要在搜索前進(jìn)行， rejected （多個(gè)最優(yōu)解）的判定要在搜索后判定。
(7) 關(guān)于出現(xiàn)相同最優(yōu)解的標(biāo)記，每出每種劃分的 sum 每出現(xiàn)一次標(biāo)記 +1 ，要使標(biāo)記為 O(1) ，只需把 vist 數(shù)組開得足夠大。 N 最多為 6 位數(shù)，因此 Maxsum=999999
簡單的附上一個(gè)關(guān)于例 50 ? 12346 的不完全搜索樹
省略號為未列出的結(jié)點(diǎn)
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)
//
得到數(shù)字字符串s前i位字符（數(shù)字）組成的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位數(shù)字構(gòu)成的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位數(shù)字構(gòu)成的int
46
{
47
return
n
%
(
int
)pow(
10.0
,(
double
)i);
48
}
49
50
int
aim;
//
目標(biāo)數(shù)
51
52
int
result;
//
最優(yōu)劃分的和
53
int
path;
//
最優(yōu)劃分的劃分方式
54
55
int
sum;
//
某種劃分的和
56
int
p;
//
某種劃分方式
57
58
int
vist[
1000000
];
//
記錄每個(gè)sum出現(xiàn)的次數(shù)
59
//
999999是當(dāng)n=999999時(shí)的最大和值
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位字符轉(zhuǎn)變?yōu)閿?shù)字留下，計(jì)入部分和
77
sum
+=
a;
//
部分和
78
if
(sum
>
aim)
//
剪枝，部分和已經(jīng)大于aim，無需繼續(xù)往下搜索
79
{
80
sum
-=
a;
81
continue
;
82
}
83
p
=
p
*
10
+
i;
//
記錄劃分方式
84
85
char
b[
7
];
//
構(gòu)造n的后i位字符序列，繼續(xù)遞歸
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
];
//
打印紙上的數(shù)字
106
cin
>>
aim
>>
s;
107
108
int
len
=
strlen(s);
109
int
n
=
getvalue(s,len);
//
構(gòu)造s的數(shù)字序列n
110
111
if
(
!
aim
&&
!
n)
112
break
;
113
114
if
(aim
==
n)
//
目標(biāo)值與打印紙上的數(shù)字一致
115
{
116
cout
<<
aim
<<
'
'
<<
n
<<
endl;
117
continue
;
118
}
119
120
int
num
=
n;
//
temporary
121
int
k
=
0
;
//
n的各位數(shù)字之和
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
)
//
最優(yōu)解多于一個(gè)
148
cout
<<
"
rejected
"
<<
endl;
149
else
if
(vist[result]
==
1
)
//
有唯一最優(yōu)解
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的第一段劃分位數(shù)，即從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
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
