import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class TwoBamboo { /* メモ化用Map */ private static Map calculatedMap; /* 2本の竹のうち短い方の竹を対象にしてナップサック問題として考える。 */ public static void main(String[] args) { Scanner cin = new Scanner(System.in); int d = cin.nextInt(); int[][][] allQuestions = new int[d][2][]; for (int i = 0; i < d; i++) { /* 2本の竹情報 */ allQuestions[i][0] = new int[2]; allQuestions[i][0][0] = cin.nextInt(); allQuestions[i][0][1] = cin.nextInt(); /* 要求数 */ int requestsNum = cin.nextInt(); /* 要求情報 */ allQuestions[i][1] = new int[requestsNum]; for (int j = 0; j < requestsNum; j++) { allQuestions[i][1][j] = cin.nextInt(); } } calculatedMap = new HashMap(); for (int[][] question : allQuestions) { System.out.println(answer(question[0], question[1])); } } /* 各データセット単位で解く */ private static int answer(int[] bamboo, int[] requests) { /* 2本の竹の総和に対し、要求された長さを小さい順に足していく。要求された長さの和が2本の竹の総和を越えたら、以降の要求には絶対に応えられないので無視する。また、長いほうの竹を越える要求も満たせないので無視する */ Arrays.sort(requests); int lengthSum = bamboo[0] + bamboo[1]; int maxRequestLength; int requestSum = 0; for (maxRequestLength = 0; maxRequestLength < requests.length; maxRequestLength++) { requestSum += requests[maxRequestLength]; if (requests[maxRequestLength] > bamboo[1] || requestSum > lengthSum) { break; } } requests = Arrays.copyOf(requests, maxRequestLength); calculatedMap.clear(); return getNum(0, bamboo[0], bamboo[1], requests, new ArrayList()); } private static int getNum(int currentIndex, int shortBamboo, int longBamboo, int[] requests, List cutIndexes) { /* 最後の要求まで達したなら終了 */ if (currentIndex >= requests.length) { return 0; } int key = currentIndex * 1000000 + shortBamboo; if (calculatedMap.containsKey(key)) { return calculatedMap.get(key); } /* 短い方の竹から切り出せなくなったら、今まで切らなかったものを順に長い方から切っていき、切れなくなったら終了 */ if (requests[currentIndex] > shortBamboo) { int result = 0; for (int i = 0; i < requests.length; i++) { if (!cutIndexes.contains(i)) { longBamboo -= requests[i]; if (longBamboo < 0) { break; } result++; } } return result; } /* 切った場合 */ List cutIndexesNext = new ArrayList(cutIndexes); cutIndexesNext.add(currentIndex); int cutNum = 1 + getNum(currentIndex + 1, shortBamboo - requests[currentIndex], longBamboo, requests, cutIndexesNext); int notCut = getNum(currentIndex + 1, shortBamboo, longBamboo, requests, cutIndexes); int result = cutNum > notCut ? cutNum : notCut; calculatedMap.put(key, result); return result; } private static void debug(int[] bamboo, int[] requests) { System.out.println("bamboo: a=" + bamboo[0] + ", b=" + bamboo[1]); for (int request : requests) { System.out.print(request + " "); } System.out.println(); } }