1.链接地址：
http://poj.org/problem?id=1416
http://bailian.openjudge.cn/practice/2803
2.题目：
3.思路：
dfs(深度优先搜索)+剪枝
4.代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib> using namespace std; int max_sum; int res_sum;
vector<int> res_path;
int count; int sum;
vector<int> path; void dfs(string str)
{
//for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
if(str.size() == )
{ if(sum <= max_sum && sum == res_sum)
{
++count;
//res_path.clear();
//for(int v_i = 0; v_i < path.size(); ++v_i) res_path.push_back(path[v_i]);
//for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
res_path = path;
}
else if(sum <= max_sum && sum > res_sum)
{
res_sum = sum;
count = ;
//for(int v_i = 0; v_i < path.size(); ++v_i) cout << path[v_i] << " "; cout << "(" << str << ")(" << sum << ")";cout << endl;
res_path = path;
//res_path.clear();
//for(int v_i = 0; v_i < path.size(); ++v_i) res_path.push_back(path[v_i]);
}
return;
} for(int i = str.size() - ; i >= ; --i)
{
string str_left = str.substr(,i);
string str_right = str.substr(i); int left = atoi(str_left.c_str());
int right = atoi(str_right.c_str()); //剪枝
if(sum + right > max_sum) continue; //剪枝二
if(res_sum == max_sum && count > ) break; sum += right;
path.push_back(right); dfs(str_left); sum -= right;
path.pop_back();
} return;
} int main()
{
//freopen("C://input.txt","r",stdin); string str;
cin >> max_sum >> str; while(max_sum != || str.size() != || str[] != '')
{
int num = atoi(str.c_str());
if(num <= max_sum)
{
cout << num << " " << num << endl;
}
else
{
sum = ;
path.clear(); res_sum = -; dfs(str); if(res_sum == -) cout << "error" << endl;
else if(count > ) cout << "rejected" << endl;
else
{
cout << res_sum;
for(int i = res_path.size() - ; i >= ; --i) cout << " " << res_path[i];
cout << endl;
}
} cin >> max_sum >> str;
} return ;
}