Luogu p1460 [usaco2.1] healthy Holstein cows

Portal ：https://www.luogu.com.cn/problem/P1460

I wrote this problem solution because my understanding of the problem is right , The thinking is clear . But in DFS There is a lack of skill in the code, which makes it impossible to write completely AC Code for . From the solution to the question, I am right DFS The parameter list of function definition has been further understood , stay DFS In the algorithm, , The definition of parameter list is also extremely important , Defining parameter lists skillfully can reduce the complexity of code , It also makes the idea of writing questions clearer .

meanwhile , To and DFS Tag access and tag removal are also clearer , It's a lot better than the first day when I didn't know where to start , Continue refueling ！

Get down to business . This topic is still a two-way search , For each feed , You can choose to add or not . It also needs to be set visit Array to save the access path . After each visit, the status at this time needs to be determined , Whether the conditions are met , If the conditions are met, return and compare the answers to determine whether to update the answers , If the conditions are not met, continue to search downward .

Code up , The notes are fairly detailed .

#include<iostream>
using namespace std;
int Vitamin[30][30] = { 0 }, Need[30] = { 0 };
// The two arrays are the vitamin content of feed , Vitamins needed by cattle 
int visit[30] = { 0 }, Anvisit[30] = { 0 }, ans = 5000;
//visit Used to store the current feed number ,Anvisit Feed number for storing answers 
//ans Store the number of answers , The initial value is a relatively large number 
int v = 0, g = 0;
//v,g Meaning the title has , Don't go into 
bool Judge(int amount)
{
	// This function is used to judge whether the requirements have been met in the current situation 
	//amount Is the total amount of feed that has been fed 
	if (!amount)return false;
	// If one kind of feed is not added directly pass
	for (int i = 1; i <= v; i++)
	{
		int sum = 0;
		for (int j = 1; j <= amount; j++)
			sum += Vitamin[visit[j]][i];
		// Add up , Calculate the content of each vitamin 
		if (sum < Need[i])return false;
		// Once there is a direct false
	}
	return true;
}
void DFS(int number,int count)
{
	//number Number the feed ,count Is the total feed 
	// Setting parameters in this way can largely avoid thinking too complicated 
	if (number > g)
		return;
	// The border 
	if (Judge(count)) {// If the conditions are met 
		if (count < ans) {// And the new answer is smaller than the original answer 
			ans = count;
			for (int i = 1; i <= count; i++)
				Anvisit[i] = visit[i];
			// Update answers 
		}
		return;
		// Mission accomplished , Go straight back to , There is no need to go down 
	}
	visit[count + 1] = number + 1;
	// Prepare to visit , Mark first 
	DFS(number + 1, count + 1);
	// Visit the next feed and add 
	visit[count + 1] = 0;
	// Access to the end , Eliminate marking 
	DFS(number + 1, count);
	// Visit the next feed without adding 
}
int main(void)
{
	scanf("%d", &v);
	for (int i = 1; i <= v; i++)
		scanf("%d", &Need[i]);
	scanf("%d", &g);
	for (int i = 1; i <= g; i++)
		for (int j = 1; j <= v; j++)
			scanf("%d", &Vitamin[i][j]);
	// A bunch of inputs 
	DFS(0, 0);
	// Pay attention to search from zero , Because number one also needs to search for two ways to add or not add 
	printf("%d", ans);
	for (int i = 1; i <= ans; i++)
		printf(" %d", Anvisit[i]);
	return 0;// End of the flower 
}