首页 > 代码库 > 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;}
View Code

 

Ppoj 1014 深搜