POJ1416 (dfs)

zhclovemyh / 2024-01-26 / 原文

POJ1416 (dfs)

公司现在要发明一种新的碎纸机，要求新的碎纸机能够把纸条上的数字切成最接近而不超过target值（可以选择不切割）。比如，target的值是50，而纸条上的数字是12346，应该把数字切成四部分，分别是1、2、34、6。因为这样所得到的和43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超过50的。（比如1, 23, 4, 和6 就不可以,因为它们的和不如43接近50，而12, 34, 6也不可以，因为它们的和超过50了。要求（如果全部超过目标数字，输出error，如果有两种及以上和一样的最小答案，输出rejected）

示例输入

50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0

示例输出

43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected

思路：切割数字的过程就是一个简单的排列组合隔板法问题，使用dfs找到各个组合，验证各个组合的和即可，判断方法是，满足条件且不与已有最小答案相等为1，满足条件但；与最小答案相等为2；没有满足条件的为0；

answer：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int pap[6];
int t, n, p;
bool flag[6];
bool cpy[6];
int ans,record;
void check(){
	int sum = 0, temp = 0;
	for(int i = 0;i <= p;i++){
		if(flag[i] || i == p){
			sum += temp;
			temp = 0;	
		}
		temp = temp * 10 + pap[i];
	}
	if(sum > ans && sum <= t) {
		record = 1;
		ans = sum;
		memcpy(cpy,flag,sizeof(flag));
	}
	else if(sum == ans) record = 2;
}
void dfs(int deep,int pre){
	if(deep == n) {
		check();
		return;
	}
	for(int i = pre + 1;i < p;i++){
		if(!flag[i]) {
			flag[i] = true;
			dfs(deep + 1, i);
			flag[i] = false;
		}
	}
}
int main() {
	char ch;
	while(1){
		scanf("%d", &t);
		if(t == 0) break;
		p = 0;
		ans = -1;
		record = 0;
		while((ch = getchar()) != '\n') {
			if(ch >= '0' && ch <= '9') {
				pap[p] = ch - '0';
				p++;
			}
		}
		memset(flag, false, sizeof(flag));
		for(n = 0;n < p;n++){
			dfs(0,0);
		}
		if(record == 0) printf("error\n");
		else if(record == 2) printf("rejected\n");
		else {
			printf("%d", ans);
			int temp = 0;
			for(int i = 0;i <= p;i++){
				if(cpy[i] || i == p){
					printf(" %d",temp);
					temp = 0;	
				}
				temp = temp * 10 + pap[i];
			}
			printf("\n");
		}
	}
	return 0;
}