Untitled
unknown
plain_text
22 days ago
2.5 kB
1
Indexable
Never
#include<iostream> using namespace std; int a[30]; int gia[30];//gia cho troi int giasale[30];//gia goi tuong ung voi goi int sale[30][30];//i la so goi, j la so linh kien co trong int countt[30];//so linh kien co trong moi goi int can[30];//so linh kien can mua int visited[30];//danh dau so linh kien can mua int n, m; int sum; int maxx; void backtrack(int u){ if(u==m+1) return; for(int c=0; c<2; c++){ bool ch=false; if(c==0){ for(int i=1; i<countt[u]; i++){ if(visited[sale[u][i]]==0){ ch = true; } } if(ch==true){ int a[30]; int dem=0; for(int i=1; i<countt[u]; i++){ if(visited[sale[u][i]]==0){ visited[sale[u][i]]=1; a[dem]=sale[u][i]; dem++; } } sum+=giasale[u]; int e=sum; for(int i=1; i<=n; i++){ if(visited[i]==0) sum+=gia[i]; } if(sum<maxx) maxx=sum; sum = e; backtrack(u+1); sum-=giasale[u]; for(int i=0; i<dem; i++){ visited[a[i]]=0; } } } else backtrack(u+1); } } int main(){ //freopen("in.txt", "r", stdin); int t; cin>>t; for(int tc=1; tc<=t; tc++){ cin>>n; for(int i=1; i<=n; i++){ cin>>gia[i]; visited[i]=0; } cin>>m; for(int i=1; i<=m; i++) countt[i]=1; int x, y; for(int i=1; i<=m; i++){ cin>>y; giasale[i]=y; cin>>x; for(int j=1; j<=x; j++){ cin>>sale[i][countt[i]++]; } } int p; cin>>p; for(int i=1; i<=p; i++) cin>>can[i]; maxx=0; for(int i=1; i<=n; i++){ int d=0; for(int j=1; j<=p; j++){ if(i==can[j]){ d++; } } if(d==0) visited[i]=1; } for(int i=1; i<=n; i++){ if(visited[i]==0) maxx+=gia[i]; } sum=0; backtrack(1); cout<<"#"<<tc<<" "; cout<<maxx<<endl; } return 0; } -------------------bai mua linh kien----------------- 1 <-- T = 1, 5 <-- Số linh kiện chính của máy tính 20 15 17 18 25 <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng 4 <-- 4 gói ưu đãi trên mạng 30 3 1 2 5 <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5 25 2 2 3 <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3 35 3 1 3 5 <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5 20 2 3 4 <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4 3 2 4 5 <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5