Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1758
The headmaster of Spring Field School is considering employing some new teachers for certain subjects. There are a number of teachers applying for the posts. Each teacher is able to teach one or more subjects. The headmaster wants to select applicants so that each subject is taught by at least two teachers, and the overall cost is minimized. Input The input consists of several test cases. The format of each of them is explained below: The first line contains three positive integers S, M and N. S (≤ 8) is the number of subjects, M (≤ 20) is the number of serving teachers, and N (≤ 100) is the number of applicants. Each of the following M lines describes a serving teacher. It first gives the cost of employing him/her (10000 ≤ C ≤ 50000), followed by a list of subjects that he/she can teach. The subjects are numbered from 1 to S. You must keep on employing all of them. After that there are N lines, giving the details of the applicants in the same format. Input is terminated by a null case where S = 0. This case should not be processed. Output For each test case, give the minimum cost to employ the teachers under the constraints.
Sample Input 2 2 2 10000 1 20000 2 30000 1 2 40000 1 2 0 0 0
Sample Output 60000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int s,m,n,c,t,ok;
string in;
vector < pair<int,int>> applicants;
int memo[1<<16][101];
int add_teacher(int cur, int bitmask) {
int exist = cur & bitmask; // already have subjects
cur |= bitmask;
cur |= (exist << 8);
return cur;
}
int solve(int bitmask, int idx) {
if(bitmask == ok) return 0 ;
else if(idx>=n) return 1e7;
else if(memo[bitmask][idx] != -1) return memo[bitmask][idx];
// exclude
int best = solve(bitmask, idx+1);
// include
best = min(best, solve(add_teacher(bitmask, applicants[idx].second), idx+1) + applicants[idx].first);
return memo[bitmask][idx] = best;
}
int main() {
while(scanf("%d %d %d\n",&s,&m,&n), (s+m+n)){
applicants.clear();
memset(memo, -1, sizeof memo);
int cost = 0;
int bitmask = 0;
ok = (1<<s)-1;
ok |= (ok<< 8);
for(int i=0;i i+It m;i++){
getline(cin,in);
istringstream iss(in);
iss >> c;
cost += c;
int subjects = 0;
while(iss >> t) {
t--;
subjects |= (1<<t);
}
bitmask = add_teacher(bitmask, subjects);
}
for(int i=0;i i+It n;i++){
getline(cin,in);
istringstream iss(in);
iss >> c;
int subjects = 0;
while(iss >> t) {
t--;
subjects |= (1 i+It t);
}
applicants.push_back({c,subjects});
}
printf("%d\n", solve(bitmask, 0)+cost);
}
}
Input
10000 1
20000 2
30000 1 2
40000 1 2
0 0 0
Output
Demonstration
UVA Online Judge solution - 10817-Headmaster's Headache - UVA Online Judge solution in C,C++,java