Untitled
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