首页 > 代码库 > Ppoj 1014 深搜
Ppoj 1014 深搜
这个题题意是给你价值1-6的珠宝个数输出能否平分为两份(如果平分为三分就不知道怎么做了……)
主要是用回溯DFS,但是要剪枝,对200取模……!!(很重要……)
代码……
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#include <cstdlib>using namespace std;int n[7];bool flag;int aver;void dfs(int num,int t){ if(flag) return; if(num == aver){ flag = 1; return; } for(int i = t;i <= 6;i++){ if(n[i] && num + i <= aver){ n[i]--; dfs(num+i,i); n[i]++; if(flag) return; } }}int main(){ //freopen("input.txt","r",stdin); int cas = 1; while(1){ int sum = 0; for(int i = 1;i <= 6;i++){ cin >> n[i]; n[i] %= 200; sum += (i*n[i]); } if(sum == 0) break; cout << "Collection #" << cas++ << ":" << endl; if(sum % 2 == 1){ cout << "Can‘t be divided." << endl << endl; continue; } aver = sum /2; flag = 0; dfs(0,1); if(flag){ cout << "Can be divided." << endl << endl; } else{ cout << "Can‘t be divided." << endl << endl; } } return 0;}
Ppoj 1014 深搜
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。