首页 > 其他 > 详细

NYOJ 927 The partial sum problem 【DFS】+【剪枝】

时间:2014-06-22 17:59:36      阅读:479      评论:0      收藏:0      [点我收藏+]

The partial sum problem

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述
One day,Tom’s girlfriend give him an array A which contains N integers and asked him:Can you choose some integers from the N integers and the sum of them is equal to K. 
输入
There are multiple test cases.
Each test case contains three lines.The first line is an integer N(1≤N≤20),represents the array contains N integers. The second line contains N integers,the ith integer represents A[i](-10^8≤A[i]≤10^8).The third line contains an integer K(-10^8≤K≤10^8).
输出
If Tom can choose some integers from the array and their them is K,printf ”Of course,I can!”; other printf ”Sorry,I can’t!”.
样例输入
4
1 2 4 7
13
4
1 2 4 7
15
样例输出
Of course,I can!
Sorry,I can‘t!

这题很经典,剪枝的时候要细心。

#include <stdio.h>
#include <stdlib.h>
int n, arr[22], sum, vis[22], ok, count;
const char *sam[] = {"Sorry,I can't!\n", "Of course,I can!\n"};

int cmp(const void *a, const void *b){
	return *(int *)a - *(int *)b;
}

void DFS(int k){
	if(count == sum){
		ok = 1; return;
	}
	
	for(int i = k; i < n; ++i){
		if(i && arr[i] == arr[i-1] && !vis[i-1]) //cut
			continue;
		if(count > sum && arr[i] > 0) return; //cut
		
		count += arr[i]; vis[i] = 1;
		DFS(i + 1);
		if(ok) return;
		count -= arr[i]; vis[i] = 0;
	}
}

int main(){
	while(scanf("%d", &n) == 1){
		for(int i = 0; i < n; ++i){
			scanf("%d", arr + i);
			vis[i] = 0;
		}
		scanf("%d", &sum);
		qsort(arr, n, sizeof(int), cmp);
		count = ok = 0; DFS(0);
		printf(ok ? sam[1] : sam[0]);
	}
	return 0;
}


NYOJ 927 The partial sum problem 【DFS】+【剪枝】,布布扣,bubuko.com

NYOJ 927 The partial sum problem 【DFS】+【剪枝】

原文:http://blog.csdn.net/chang_mu/article/details/32140951

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!