nangcapmaytinhquocdepzai

 avatar
quoc14
c_cpp
a month ago
1.7 kB
1
Indexable
Never
caidat
#include <iostream>

using namespace std;

int n;
int a[200];
int m;

int dem[200];
struct docanmua {
	int num_buy;
	int L[100]; 
};

struct goikhuyenmai {
	int num_sale;
	int gia;
	int M[100];
};


docanmua x;
goikhuyenmai y[100];
int damua[100];
int minGia;

bool checkFull() {
	
	for (int i = 1; i <= x.num_buy; i++) {
		if (dem[x.L[i]] == 0) return false;
	}
	return true;

}

void update(int k, int x) {
	for (int i = 1; i <= y[k].num_sale; i++) {
		dem[y[k].M[i]] += x;
	}
}
// k goi khuyen mai

void backtrack(int k, int curPrice) {
	if (curPrice > minGia) return;
	if (checkFull()) {
		if (curPrice < minGia) minGia = curPrice;
		return;
	}

	if (k == m + 1) {
		for (int i = 1; i <= x.num_buy; i++) {
			if (dem[x.L[i]] == 0) {
				curPrice += a[x.L[i]];
			}
		}
		if (curPrice < minGia) minGia = curPrice;
		return;
	}

	for (int i = 0; i < 2; i++) {
		// mua
		if (i == 1) {
			update(k, 1);
			backtrack(k + 1, curPrice + y[k].gia);
			update(k, -1);


		}
		// k mua
		else {
			backtrack(k + 1, curPrice);
		}
	}

}	

void solve(int testcase) {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> y[i].gia;
		cin >> y[i].num_sale;
		for (int j = 1; j <= y[i].num_sale; j++) {
			cin >> y[i].M[j];	
		}
	}
	cin >> x.num_buy;
	for (int i = 1; i <= x.num_buy; i++) {
		cin >> x.L[i];
	}
	minGia = 1e8;
	backtrack(1, 0);
	cout << "#" << testcase << " " << minGia << endl;
}

int main() {
	

	int t; cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}


	return 0;
}
Leave a Comment