题目描述:
http://poj.org/problem?id=1416
中文大意:
要求编写一个碎纸机程序。
待碎纸张上仅包含数字,切割后,每个碎片上也都会有一个或多个数字。
给定一个目标数字,要求所有碎纸上的数字之和尽可能地接近目标数字,但不能越过该数字。
还有三个特殊规则:
1.如果目标数字与纸张上的数字相同,则不用裁切。
2.如果无解,则输出“error”。
3.如果最接近目标数字的解有多种可能,则输出“rejected”。
思路:
假设待碎纸张上有 N 个数字,尝试从最左端开始,切一定数量的数字。
一共有 N 种切法:切 1 个数字,切 2 个数字......
剩余纸张,继续以这种方法切割,直至切割完成。
代码:
#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<sstream> using namespace std; int t,num; int parts[6];//各碎片的数值大小 bool results;//是否有多组解 int end_sum,end_k;//用来记录最优数据 int end_parts[6]; //str:未粉碎部分 //k:当前碎片个数 void dfs(string str, int k){ //纸片粉碎完成 if(str.length() == 0){ //计算所有碎片之和 int sum = 0; for(int i=0;i<k;i++){ sum += parts[i]; } //题目要求 sum 应 <= t if(sum <= t){ //已经有了满足条件的一组解 if(sum == end_sum){ results = true; } else if(sum > end_sum){//更优解 end_sum = sum; for(int i=0;i<k;i++){ end_parts[i] = parts[i]; } end_k = k; results = false; } } return; } //p1:已切割部分 //p2:剩余部分 string p1,p2; //尝试切割 i个数字 for(int i=1;i<=str.length();i++){ p1 = str.substr(0,i); //纸条还有剩余 if(i != str.length()){ p2 = str.substr(i); } else{//切割全部,没有剩余 p2 = ""; } //string -> int istringstream iss(p1); iss >> parts[k]; //继续切割剩余部分 dfs(p2, k+1); } } int main(){ while(scanf("%d %d", &t, &num) && (t || num)){ end_sum = -1; results = false; //int -> string ostringstream oss; oss << num; dfs(oss.str(), 0); if(results){ printf("rejected\n"); } else if(end_sum == -1){ printf("error\n"); } else{ printf("%d", end_sum); for(int i=0;i<end_k;i++){ printf(" %d", end_parts[i]); } printf("\n"); } } }