//暴力穷举法
#include <iostream>
#include <vector>

using namespace std;

int result_num = 0;

//打印vector
template <typename T>
void print_vector(vector<T> vec) {
	cout << '[';
	//遍历输出，空格间隔
	for (auto i = vec.begin(); i != vec.end(); i++) {
		if (i + 1 == vec.end())
			cout << *i << ']' << endl;
		else
			cout << *i << " ";
	}
}

//计算方案result所需花销
int cal_cost(const vector<int>& results, const vector<int>& costs) {
	int cost = 0;
	for (size_t i = 0; i < results.size(); i++)
	{
		cost += results[i] * costs[i];
	}
	return cost;
}

//判断方案results花销够不够
bool cost_enough(int all_cost, const vector<int>& results, const vector<int>& costs) {
	return all_cost >= cal_cost(results, costs);
}

//判断方案是否可行
bool good_result(int all_cost, const vector<int>& results, const vector<int>& costs) {
	return all_cost == cal_cost(results, costs);
}

//判断喜爱程度是否满足要求
bool good_favor(const vector<int>& results, const vector<int>& favors) {
	//遍历favors
	for (int i = 0; i < favors.size() - 1; i++) {
		//如果后一个零食个数不为0
		if (results[favors[i + 1]] != 0) {
			if (results[favors[i]] <= results[favors[i + 1]])
				return false;
		}
	}
	return true;
}

//暴力穷举，
void solve(int all_cost, int ope_index, const vector<int>& costs, const vector<int>& favors, vector<int>& results) {
	//只要花销够，就继续循环
	while (cost_enough(all_cost, results, costs)) {
		//如果花销刚好花完
		if (good_result(all_cost, results, costs)) {
			//如果满足喜爱程度要求,则解+1
			if (good_favor(results, favors)) {
				result_num++; 
				print_vector<int>(results);
			}
			//返回上级
			results[ope_index] = 0;
			return;
		}
		//不拿当前零食
		//如果不是最后一个零食，处理下一个零食
		if (ope_index + 1 < costs.size())
			solve(all_cost, ope_index + 1, costs, favors, results);
		else
		{
			//剩余开销
			int left_cost = all_cost - cal_cost(results, costs);
			//如果刚好用完，且满足要求，解+1
			if (left_cost%costs[ope_index] == 0 && good_favor(results, favors)) {
				results[ope_index] = left_cost / costs[ope_index];
				result_num++;
				print_vector<int>(results);
			}
			//返回上级
			results[ope_index] = 0;
			return;
		}
		//拿当前零食，继续循环
		results[ope_index]++;
	}
	//如果花销不够，当前拿取数清零，返回上级
	results[ope_index] = 0;
	return;
}

int main()
{
	//输入
	int case_num;//案例数
	cin >> case_num;
	for (int c = 0; c < case_num; c++) {

		int all_cost, snack_num;//总开销，零食种类数
		int favor_num;//喜爱零食的数量
		vector<int> costs;//开销列表
		vector<int> favors;//喜爱程度列表，越靠前越喜

		cin >> all_cost >> snack_num;
		for (int i = 0; i < snack_num; i++) {
			int cost;
			cin >> cost;
			costs.push_back(cost);
		}
		cin >> favor_num;
		for (int i = 0; i < favor_num; i++) {
			int snack;
			cin >> snack;
			favors.push_back(snack);
		}
		//暴力穷举
		vector<int> results;
		for (size_t i = 0; i < costs.size(); i++)
		{
			results.push_back(0);
		}
		solve(all_cost, 0, costs, favors, results);
		//打印结果
		cout << "result number:" << result_num % 100000 << endl;
		//结果清零
		result_num = 0;
	}
	
}
/*
input:
2
10 3
4 5 6
2
0 1
20 5
2 4 5 6 7
2
1 2
*/

运行结果

解法2，深度优先遍历，分两个数组，一个存储有优先级的零食，优先级越高的零食越靠前，另一个存储无优先级的零食。
代码主体如下：

class Solution {
	const static bool debug = false;
	const static int mod = 100000;
	int C, n, m, ans = 0;
	//nums0中有优先级，nums1中无
	vector<int> nums0, nums1;
	//对nums1处理
	void dfs1(int i, int cost) {
		if (debug)
			cout << "dfs1 i=" << i << " cost=" << cost << endl;
		if (cost == C) {
			++ans;
			if (debug)
				printf("update ------------- ans:%d --------------- \n", ans);
		}
		else if (cost > C || i >= nums1.size())
			return;
		else {
			for (int count = 0; cost + count * nums1[i] <= C; count++)
				dfs1(i + 1, cost + count * nums1[i]);
		}
	}
	//拿不拿第i个，当前消费为cost
	void dfs(int i, int cost, int lastCount) {
		if (debug)
			cout << "dfs i=" << i << " cost=" << cost << " lastCount=" << lastCount << endl;
		//越界
		if (cost > C)
			return;
		//nums0拿完之后，开始拿nums1
		if (i == nums0.size())
			dfs1(0, cost);
		//出口
		else if (cost == C) {
			++ans;
			if (debug)
				printf("update ------------- ans:%d --------------- \n", ans);
		}
		//递归
		else {
			//拿i的个数小于lastCount
			for (int count = 0; count < lastCount
				&& cost + count * nums0[i] <= C; count++)
				dfs(i + 1, cost + count * nums0[i], count);
		}
	}
public:
	Solution(int c) {
		C = c;
		cin >> n;
		vector<int> nums;
		int temp;
		for (int i = 0; i < n; i++){
			cin >> temp;
			nums.push_back(temp);
		}
		cin >> m;
		for (int i = 0; i < m; i++){
			cin >> temp;
			nums0.push_back(nums[temp]);
			nums[temp] = -1;
		}
		for (int num : nums)
			if (num != -1)
				nums1.push_back(num);
	}
	void solve() {
		//不拿nums0
		dfs1(0, 0);
		//先拿nums0再拿nums1
		dfs(0, 0, INT_MAX);
		cout << ans % mod << endl;
	}
};

int main() {
	int c;
	while (cin >> c) {
		Solution s(c);
		s.solve();
	}
	return 0;
}