工作安排

	//利用回溯法求解.



	//题意有两个地方没说清楚：1、一个人只能做一项工程，而不能分饰两角；



	//                      2、有几个工程师，每个工程师有一个工作即满足题意，不用6项工作全部都要有人做。



	//前一个人选了哪项工作，直接影响后一个人的选择余地。



	//所以需要用一个set记录在当前这个人选择之前，前面那些人已经选了的工作，进而他只能选除set中已有剩下的工作。



	//当考察完最后一个人，情况数+1（递归出口），证明是满足题意的方案。下面是代码



	



	import java.util.HashSet;
import java.util.Scanner;

//网易：工程师与项目的匹配

public class Wangyi_WorkAndWorker {
	
	private static int cases = 0; 
	
	public static void main(String[] args)
	{
		//读取输入
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String[] ables = new String[n];
		for(int i = 0; i < n; i++) 
			ables[i] = in.next();

		//计算
		backtracing(ables, 0, new HashSet<Integer>());

		System.out.println(cases);
		
		in.close();
	}
	
	
	public static void backtracing(String[] ables, int index, HashSet<Integer> set){
		
		if(index >= ables.length){
			cases++;
			return;
		}
		
		String able = ables[index];
		for(int i = 0; i < able.length(); i++){
			
			int work = able.charAt(i) - '0';
			if(!set.contains(work)) {
				set.add(work);
				backtracing(ables, index + 1, set);
				set.remove(work);
			}
		}
	}
}

package go.jacob.day914;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * [编程题]工作安排
 * 
 * @author Jacob 
 * 利用回溯法求解
 * 
 * 需要说明的是：
 * 不必每一项工作都有人做，只要每个人都分配到工作即可
 * 
 */
public class Demo1 {
	public static int count = 0;
	public static Set<Integer> set;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] strs = new String[n];
		set = new HashSet<Integer>();
		for (int i = 0; i < n; i++) {
			strs[i] = sc.next();
		}
		for (int i = 0; i < 6; i++) {
			set.add(i);
		}
		solve(strs, 0);
		System.out.println(count);
		sc.close();
	}

	private static void solve(String[] strs, int k) {
		if (k == strs.length) {
			count++;
			return;
		}

		for (char c : strs[k].toCharArray()) {
			if (set.contains(c - '0')) {
				set.remove(c - '0');
				solve(strs, k + 1);
				set.add(c - '0');
			}
		}
	}
}

n=int(raw_input())
joblist=[]
for i in range(n):
    joblist.append(raw_input().strip())
def work_assign(i,joblist,res):
    result=0
    for k in joblist[i]:
        if k not in res:
            if i==n-1:
                result+=1
            else:
                result+=work_assign(i+1,joblist,res+[k])
    return result
print(work_assign(0,joblist,[]))

跟背包放法问题相似

import java.util.Scanner;

public class Main {
    static int count = 0;
    static int n = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        count = 0;
        n = in.nextInt();
        String[] ability = new String[n];
        for (int i = 0; i < n; i++) {
            ability[i] = in.next();
        }
        generate(ability,0, 0);
        System.out.println(count);
    }

    private static void generate(String[] ability,int peopleNumber, int current) {
        String s=ability[peopleNumber];
        if (peopleNumber == n-1) {
            for(int i=0;i<s.length();i++){
                int job=s.charAt(i)-'0';
                if ((current&(1<<job))==0){
                    count++;
                }
            }
        } else {
            for(int i=0;i<s.length();i++){
                int job=s.charAt(i)-'0';
                if ((current&(1<<job))==0){
                    generate(ability,peopleNumber+1,current|(1<<job));
                }
            }
        }
    }
}

/*
这道题目题意有点模糊
其实意思是：
1、所有工程师都必须有事可做，且只能做一件事情。
2、不必所有事都要做。	 
下面的代码就是实现上述功能 
*/

#include <iostream>
using namespace std;
#include<string.h>
#define N 6

int sum = 0;
int b[N] = {0}; //记录工作是否被做过 
int main(int argc, char *argv[])
{
	void fun(string a[], int m, int k);
	string a[N]; 
	int k;
	cin>>k;
	for(int i = 0; i < k; i++)
		cin>>a[i];
	
	fun(a, 0, k);
	cout<<sum<<endl;
	return 0;
}

//回溯法求解 
void fun(string a[], int m, int k) 
{
	if (m == k) {
		sum++;
	}	
	else {
		for (int j = 0; j < a[m].size(); j++) {
			int temp = (int)(a[m][j] - '0');
			if (b[temp] == 0) {
				b[temp] = 1;
				fun(a, m + 1, k);
				b[temp] = 0;
			}		 
		}
	}
}

#include <iostream>
#include <vector>
#include<set>
#include<string>
using namespace std;
 
void backtracing(string str[], int index,int n, set<int> sev);
 
int cases = 0;
int main()
{
    int n = 0;
    cin >> n;
    string str[6];
    int index = 0;
    set<int> sev ;
    for (int i = 0; i < n; ++i)
    {
        cin>>str[i];
    }
    backtracing(str, 0, n, sev);
    cout << cases << endl;
}
void backtracing(string str[], int index,int n, set<int> sev)
{
    if (index == n)
    {
        ++cases;
        return;
    }
    string str0 = str[index];
    for (int i = 0; i < str0.length(); i++){
 
        int work = str0[i] - '0';
        if (sev.find(work)==sev.end()) {
            sev.insert(work);
            backtracing(str, index + 1,n, sev);
            sev.erase(work);
        }
    }
}

n = int(input())
canDo = [input() for _ in range(n)] 
done = [False] * 6

def solve(i):
    
    if i == n:
        return 1
    
    res = 0
    for k in range(6):
        if not done[k] and (str(k) in canDo[i]):
            done[k] = True
            res += solve(i+1)
            done[k] = False
    return res

print(solve(0))

#include <iostream>
#include <vector>
using namespace std;
 
int queenProblem(const vector<vector<bool>> &a, vector<bool> &mask, int id)
{
    int i, sum = 0;
    for(i = 0; i < 6; i++)
        if (a[id][i] && mask[i])
        {
            if (id == 0)
                sum += 1;
            else
            {
                mask[i] = false;
                sum += queenProblem(a, mask, id - 1);
                mask[i] = true;
            }
        }
    return sum;
}
 
 
int main()
{
    int n, i, j;
    cin >> n;
    vector<vector<bool>> a(n, vector<bool>(6, false));
    string str;
    for (i = 0; i < n; i++)
    {
        cin >> str;
        for (j = 0; j < str.length(); j++)
            a[i][str[j] - '0'] = true;
    }
    vector<bool> mask(6, true);
    cout << queenProblem(a, mask, n - 1) << endl;;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int ans;
vector<vector<int>> able(10, vector<int>(0));
int work[10];
void init()
{
    for (int i = 0; i < 10; i++)
        able[i].clear();
}
void dfs(int i)
{
    if (i == n + 1) 
    {
        ans++;
        return;
    }
    else
    {
        int len = able[i].size();
        for (int j = 0; j < len; j++)
        {
            int v = able[i][j];
            if (!work[v])
            {
                work[v] = 1;
                dfs(i + 1);
                work[v] = 0;
            }
        }
    }
}
int main()
{
    while (cin >> n)
    {
        ans = 0;
        init();
        memset(work, sizeof(work), 0);
        string s;
        for (int i = 1; i <= n; i++)
        {
            cin >> s;
            for (int j = 0; j < s.size(); j++)
                able[i].push_back(s[j] - '0');
        }
        dfs(1);
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

import sys


class Solution:
    def get_work_assignment(self, arr):
        count = [0]
        for i in arr[0]:
            self.process(arr, i, 1, count)
        print(count[0])

    def process(self, arr, path, level, count):
        if level == len(arr):
            count[0] += 1
            return

        for i in arr[level]:
            if i not in path:
                self.process(arr, path+i, level+1, count)


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    args = list()
    for _ in range(n):
        args.append(sys.stdin.readline().strip())
    solution = Solution()
    solution.get_work_assignment(args)

import java.util.Scanner;

/*
 * 非常典型的dfs解题方法，然后使用visited防止元素重复访问
 * */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            n = scanner.nextInt();
            String[] strs = new String[n];
            for (int i = 0; i < n; i++) {
                strs[i] = scanner.next();
            }
//            有六项任务
            boolean[] used = new boolean[6];
            dfs(used, strs, 0);
            System.out.println(count);
        }
    }

    private static int count = 0;
    private static int n = 0;

    private static void dfs(boolean[] visited, String[] strings, int cur) {
        if (cur == n) {
            count++;
            return;
        }
        String curS = strings[cur];
        for (int i = 0; i < curS.length(); i++) {
            int tmp = curS.charAt(i) - '0';
            if (!visited[tmp]) {
                visited[tmp] = true;
                dfs(visited, strings, cur + 1);
                visited[tmp] = false;
            }
        }
    }
}

//答案是我抄的
//回溯法
import java.util.HashSet;
import java.util.Scanner;

public class Main{
    
    private static int result = 0;   //需要将result作为全局变量，result为情况种类

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        /*
         * 6
012345 012345 012345 012345 012345 012345
         */
        
        /*
         * 使用回溯法，回溯法利用递归特性，将路径看做栈，当前n-1个都符合情况，在n的时候不符合情况的时候
         * 回溯到n-2的时候，重新定义n-1递归
         */
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String [] array = new String [n];    // 输入，012345存入array[i]中
        for(int i = 0;i < n;i++){
            array[i] = scanner.next();
        }
        //computing
        backtracing(array,0,new HashSet<>()); //创建新的hashset保存已经被选了的工作
        System.out.println(result);
    }
    
    public static void backtracing(String [] array,int index,HashSet<Integer> set){
        if(index >= array.length){            //递归出口，找到一个可行解，则result++再return
            result++;
            System.out.println("array,length = "+array.length);
            return;
        }
        
        String arraynew = array[index];
        for(int i = 0;i < arraynew.length();i++){
            int work = arraynew.charAt(i) - '0';
            if(!set.contains(work)){
                set.add(work);
                backtracing(array, index+1, set);
                set.remove(work);
            }
        }
    }

}

	#include<iostream>



	#include<vector>



	#include<algorithm>



	#include<string>



	using namespace std;



	 



	intplace(vector<vector<int>>& v, intstart, vector<int>& visited);



	 



	intmain() {



	    intn;



	    cin >> n;



	    vector<vector<int>> v;



	    for(inti = 0; i < n; ++i) {



	        vector<int> vec;



	        string s;



	        cin >> s;



	        for(intj = 0; j < s.size(); ++j) {



	            vec.push_back(s[j] - '0');



	        }



	        v.push_back(vec);



	    }



	    vector<int> visited(6, 0);



	    intres = place(v, 0, visited);



	    cout << res << endl;



	}



	 



	intplace(vector<vector<int>>& v, intstart, vector<int>& visited) {



	    if(start == v.size()) {



	        return1;



	    }



	    intres = 0;



	    for(inti = 0; i < v[start].size(); ++i) {



	        intnum = v[start][i];



	        if(visited[num] == 0) {



	            visited[num] = 1;



	            res += place(v, start + 1, visited);



	            visited[num] = 0;



	        }



	    }



	    returnres;



	}

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        in.nextLine();
        String[] skills=new String[n];
        for(int i=0;i<n;i++)
        {
            skills[i]=in.nextLine();
        }
        
        HashSet<Character> done=new HashSet<Character>();
        System.out.println(getTaskAllocationNum(skills,0,done));
    }
    
    public static int getTaskAllocationNum(String[] skills,int index,HashSet<Character> done)
    {
        if(index==skills.length)
        {
            return 1;
        }
        else
        {
            int num=0;
            for(int i=0;i<skills[index].length();i++)
            {
                if(!done.contains(skills[index].charAt(i)))
                {
                    done.add(skills[index].charAt(i));
                    num+=getTaskAllocationNum(skills,index+1,done);
                    done.remove(skills[index].charAt(i));
                }
            }
            return num;
        }
    }
}

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
void dfs(vector<string>& person, vector<int>& task, int taskcount, int& res, int next){
    if(taskcount==person.size()){
        res++;
        return;
    }
    int i=next,j,n=person.size();
    int m = person[i].size();
    for(j=0;j<m;j++){
        if(task[person[i][j]-'0']==0){
            task[person[i][j]-'0']=1;
            dfs(person,task,taskcount+1,res,next+1);
            task[person[i][j]-'0']=0;
        }
    }
}
 
int main(){
    int n;
    cin>>n;
    string s="";
    vector<string> person(n,s);
    vector<int> task(6,0);
    int res=0;
    for(int i=0;i<n;i++){
        cin>>s;
        person[i]=s;
    }
    dfs(person,task,0,res,0);
    cout<<res<<endl;
    return 0;
}

package Wangyi2017;
import java.util.Scanner;
public class WorkArrange {
	public static int res=0;
	public static int [] a=new int[6];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			int n=sc.nextInt();
			String []arr=new String[n];
			sc.nextLine();
			for(int i=0;i<n;i++)
			{
				arr[i]=sc.nextLine();
			}
			arrange(arr,n);
			System.out.println(res);
			res=0;
		}
		sc.close();
	}
	public static void arrange(String []arr,int n)
	{		
		if(n==0)
		{
			res++;			
			return;
		}
		for(int i=0;i<arr[n-1].length();i++)
		{
			if(a[arr[n-1].charAt(i)-'0']!=0)
			{
				continue;
			}
			else {				
				a[arr[n-1].charAt(i)-'0']=1;
				arrange(arr, n-1);
				a[arr[n-1].charAt(i)-'0']=0;
			}
		}		
	}
}