Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
1
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int T, N, M, L, result;
	static int[][] cand = new int[25][35];
	static int[][] packageItem = new int[35][25];
	static int[] buyed = new int[25];

	static int[] originPrize = new int[25];
	static int[] packagePrize = new int[35];
	static int[] packageCount = new int[35];
	static int[] needItem = new int[25];
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			System.out.print("#" + test_case);
			N = sc.nextInt();
			formatData();

			for (int i = 1; i <= N; i++) {
				originPrize[i] = sc.nextInt();
			}
			M = sc.nextInt();
			int itemName;
			for (int i = 1; i <= M; i++) { // i là gói thứ i trong M gói
				packagePrize[i] = sc.nextInt();
				packageCount[i] = sc.nextInt(); //packageCount là số sản phẩn trong gói i
				for (int j = 1; j <= packageCount[i]; j++) { // j là linh kiện thứ j có trong gói i
					itemName = packageItem[i][j] = sc.nextInt();
					cand[itemName][0]++; //cand[itemName][0] là tổng số gói có chứa linh kiện itemName
					cand[itemName][cand[itemName][0]] = i; // luu la số thứ tự của gói để có thể truy cập 
				}
			}
			L = sc.nextInt();
			for (int i = 1; i <= L; i++) {
				needItem[i] = sc.nextInt();
			}

			buy(0, 1);
			System.out.println(" " + result);

		}
	}

	static void formatData() {
		result = 2000000000;
		for (int i = 1; i <= 20; i++) {
			buyed[i] = cand[i][0] = 0;
		}
	}

	static void buy(int re, int count) {
		if (re > result) {
			return;
		}
		if (count == L + 1) {
			result = re < result ? re : result;
			return;
		}
		int needItemName = needItem[count];
		if (buyed[needItemName] > 0) {
			buy(re, count + 1);
		} else {
			buyed[needItemName]++;
			buy(re + originPrize[needItemName], count + 1);
			buyed[needItemName]--;

			for (int c = 1; c <= cand[needItemName][0]; c++){ // c là số gói có chứa linh kiện needItemName
				//cand[needItemName][c] là gói thứ i
				for (int n = 1; n <= packageCount[cand[needItemName][c]]; n++) { // day la hanh dong mua gói cand[needItemName][c] 
					buyed[packageItem[cand[needItemName][c]][n]]++;// cập nhất tất cả các linh kiện cùng gói
				}
				buy(re + packagePrize[cand[needItemName][c]], count + 1);
				for (int n = 1; n <= packageCount[cand[needItemName][c]]; n++) {
					buyed[packageItem[cand[needItemName][c]][n]]--;
				}
			}
		}
	}

}