Untitled

 avatar
unknown
plain_text
a year ago
4.0 kB
5
Indexable
#pragma warning(disable:4996)
#include <iostream> 
using namespace std; 


int minBuy;
bool buyFinish(int* buyItem, int n){
	for(int i = 1; i < n; i++){
		if(buyItem[i] == 1) return false;
	}
	return true;
}

bool check(int** package, int* value, int* buyItem, int n, int packBuy, int cost, int* isBuy){
	if(packBuy < n && isBuy[packBuy] == 1){
		return false;
	}
	for(int i = 1; i < n; i++){
		if(package[packBuy][i] == 1 && buyItem[i] == 1)
			return true;
	}
	return false;
}
void backtracking(int** package, int* value, int* buyItem, int n, int m, int packBuy, int cost, int* isBuy){
	if(cost > minBuy){
		return;
	}
	if(packBuy == n + m){
		if(buyFinish(buyItem, n)){
			if(minBuy > cost){
				minBuy = cost;
			}
		}
		return;
	}
	if(check(package,value,buyItem,n,packBuy,cost,isBuy)){
		for(int i = 1; i < n; i++){
			if(package[packBuy][i] == 1){
				buyItem[i]--;
			}
		}
		backtracking(package,value,buyItem,n,m,packBuy+1,cost+value[packBuy]);
		for(int i = 1; i < n; i++){
			if(package[packBuy][i] == 1){
				buyItem[i]++;
			}
		}
	}
	backtracking(package,value,buyItem,n,m,packBuy+1,cost,isBuy);

}

int main(){
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int t = 1; t <= T; t++){
		int n;
		cin >> n;
		n += 1;
		int** package = new int*[52];
		for(int i = 0; i < 52; i++){
			package[i] = new int[n]();
		}
		int* value = new int[52];
		int* isBuy = new int[n]();
		for(int i = 1; i < n; i++){
			cin >> value[i];
			package[i][i] = 1;
		}
		int m;
		cin >> m;
		for(int i = n; i < m+n;i++){
			cin >> value[i];
			int numItems;
			cin >> numItems;
			for(int j = 0; j < numItems; j++){
				int item;
				cin >> item;
				if(value[item] > value[i]) isBuy[item] = 1;
				package[i][item] = 1;
			}
		}
		int numBuy;
		cin >> numBuy;
		int* buyItem = new int[n];
		for(int i = 0; i< numBuy; i++){
			int item;
			cin >> item;
			buyItem[item] = 1;
		}
		minBuy = 2147483647;
		backtracking(package,value,buyItem,n,m,1,0,isBuy);
		cout << '#'<<t<<' '<<minBuy<<endl;
		for(int i = 0; i < 52;i++){
			delete[] package[i];
		}
		delete[] isBuy;
		delete[] package;
		delete[] value;
		delete[] buyItem;
	}
	return 0;
}

//struct SALE{ 
//	int P; //money 
//	int K; //size 
//	int B[21]; 
//}; 
//int N, G[21]; 
//int M, L, A[21], C[21]; 
//bool isBuy[21]; //nen mua vat k rieng le ko 
//SALE S[31]; 
//int Answer; 
//void buy(int k, int price){ //check nhanh can 
//	if(price >= Answer) return; //check basic 
//	if(k > N+M){ 
//		for(int i = 0; i < L; i++) 
//			if(C[A[i]] == 0) return; //
//		//cout << Answer << " " << price << endl; 
//		if(Answer > price) Answer = price; 
//		return; 
//	} 
//	if(k <= N){ //khong mua vat k 
//		buy(k+1, price); //check vat k co can de mua hay ko
//		if(isBuy[k]){ //mua vat k 
//			C[k]++; 
//			buy(k+1, price + G[k]); 
//			C[k]--; 
//		} 
//	}else{ //khong mua goi k-N 
//		buy(k+1, price); //mua goi k-N 
//		for(int i = 0; i < S[k-N].K; i++) 
//			C[S[k-N].B[i]]++; 
//		buy(k+1, price + S[k-N].P); 
//		for(int i = 0; i < S[k-N].K; i++) 
//			C[S[k-N].B[i]]--; 
//	} 
//} 
//int main(){ 
//	int test, T, i, j; 
//	freopen("input.txt", "r", stdin); 
//	cin >> test; 
//	for(T = 1; T <= test; T++){ 
//		cin >> N; 
//		for(i = 1; i <= N; i++){ 
//			cin >> G[i]; 
//			C[i] = -1; 
//			isBuy[i] = true; 
//		} 
//		cin >> M; 
//		for(i = 1; i <= M; i++){ 
//			cin >> S[i].P >> S[i].K; 
//			for(j = 0; j < S[i].K; j++){ 
//				cin >> S[i].B[j]; //check gia goi chua vat k nho hon gia mua vat k 
//				if(S[i].P < G[S[i].B[j]]){ 
//					isBuy[S[i].B[j]] = false; 
//				} 
//			} 
//		} 
//		Answer = 0; 
//		cin >> L; 
//		for(i = 0; i < L; i++){ 
//			cin >> A[i]; 
//			Answer += G[A[i]]; 
//			C[A[i]] = 0; 
//		} //bat dau mua tu vat 1 voi price 0 
//		buy(1, 0); 
//		cout << "#" << T << " " << Answer << endl; 
//	} 
//	return 0; 
//}
Editor is loading...
Leave a Comment