背包问题变体 - 暴力搜索 - 深度优先搜索 (递归)

青旅半醒 2023-02-13 17:09 2阅读 0赞

#  背包问题变体 - 暴力搜索 - 深度优先搜索 (递归) #

## 1. 暴力搜索 ##

### 1.1 `D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\input.txt` ###

已知总能量 (130 J) 和总路程 (30 KM)，5 个档位每千米花费时间和消耗能量，不能超过总能量 (130 J)，档位任意选择跑完总路程 (30 KM)，最少消耗时间。

2
    130 30 // 130 = 能量 (J)，30 = 路程 (KM)
    4 50 7 // 每千米需要跑 4 分钟 50 秒，消耗能量 7 (J)
    5 0 5 // 每千米需要跑 5 分钟 0 秒，消耗能量 5 (J)
    5 10 4 // 每千米需要跑 5 分钟 10 秒，消耗能量 4 (J)
    5 20 3 // 每千米需要跑 5 分钟 20 秒，消耗能量 3 (J)
    5 30 2 // 每千米需要跑 5 分钟 30 秒，消耗能量 2 (J)
    130 30
    4 50 7
    5 0 5
    5 10 4
    5 20 3
    5 30 2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

### 1.2 暴力搜索 - yongqiang.cpp ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int inference(int map[5][4], int H, int D)
    {
    	int ret = 0;
    	int amount = 0;
    	int addtime = 0;
    	int addergy = 0;
    	int mintime = INT_MAX;
    
    	for (int i = 0; i <= D; i++)
    	{
    		for (int j = 0; j <= D; j++)
    		{
    			if ((i + j) > D)
    			{
    				continue;
    			}
    
    			for (int k = 0; k <= D; k++)
    			{
    				if ((i + j + k) > D)
    				{
    					continue;
    				}
    
    				for (int m = 0; m <= D; m++)
    				{
    					if ((i + j + k + m) > D)
    					{
    						continue;
    					}
    
    					for (int n = 0; n <= D; n++)
    					{
    						if (D == (i + j + k + m + n))
    						{
    							amount++;
    							addergy = i* map[0][2] + j* map[1][2] + k* map[2][2] + m* map[3][2] + n* map[4][2];
    							if (addergy > H)
    							{
    								continue;
    							}
    
    							addtime = i* map[0][3] + j* map[1][3] + k* map[2][3] + m* map[3][3] + n* map[4][3];
    							if (addtime < mintime)
    							{
    								mintime = addtime;
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    
    	cout << "amount: " << amount << endl; // 46376
    	cout << "mintime: " << mintime << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    		int H = 0, D = 0;
    		int map[5][4] = { 0 };
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    		}
    
    		ret = inference(map, H, D);
    
    		cout << "CASE #" << i << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

Start of the program, start = 0
    Start of the program, start = 0
    
    amount: 46376
    mintime: 9200
    CASE #1 = 9200
    amount: 46376
    mintime: 9200
    CASE #2 = 9200
    
    End of the program, end = 11
    End of the program, end = 11
    Total time taken by CPU: 0.011000
    Exiting of the program...
    请按任意键继续. . .

### 1.3 暴力搜索 - yongqiang.cpp ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int inference(int map[5][4], int H, int D)
    {
    	int ret = 0;
    	int amount = 0;
    	int addtime = 0;
    	int addergy = 0;
    	int mintime = INT_MAX;
    
    	for (int i = 0; i <= D; i++)
    	{
    		for (int j = 0; j <= D; j++)
    		{
    			if ((i + j) > D)
    			{
    				continue;
    			}
    
    			for (int k = 0; k <= D; k++)
    			{
    				if ((i + j + k) > D)
    				{
    					continue;
    				}
    
    				for (int m = 0; m <= D; m++)
    				{
    					if ((i + j + k + m) > D)
    					{
    						continue;
    					}
    
    					for (int n = 0; n <= D; n++)
    					{
    						if (D == (i + j + k + m + n))
    						{
    							amount++;
    							addergy = i* map[0][2] + j* map[1][2] + k* map[2][2] + m* map[3][2] + n* map[4][2];
    							if (addergy > H)
    							{
    								continue;
    							}
    
    							addtime = i* map[0][3] + j* map[1][3] + k* map[2][3] + m* map[3][3] + n* map[4][3];
    							if (addtime < mintime)
    							{
    								mintime = addtime;
    							}
    						}
    					}
    				}
    			}
    		}
    	}
    
    	cout << "amount: " << amount << endl; // 46376
    	cout << "mintime: " << mintime << "second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    		int H = 0, D = 0;
    		int map[5][4] = { 0 };
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    		}
    
    		ret = inference(map, H, D);
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    amount: 46376
    mintime: 9200second
    CASE #1 = 153 20
    amount: 46376
    mintime: 9200second
    CASE #2 = 153 20
    
    End of the program, end = 13
    End of the program, end = 13
    Total time taken by CPU: 0.013000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

## 2. 深度优先搜索 (递归) ##

### 2.1 深度优先搜索 (递归) 1 ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    void dfs_v1(const int map[5][4], const int H, const int D, int sumtime, int sumergy, int step, int count, int *mintime)
    {
    	computation++;
    
    	if (sumergy > H) {
    		return;
    	}
    
    	if (sumtime >= *mintime) {
    		return;
    	}
    
    	if (count >= D)
    	{
    		if (sumtime < *mintime)
    		{
    			*mintime = sumtime;
    		}
    
    		return;
    	}
    
    	if (step >= 5) {
    		return;
    	}
    
    	if (sumergy + map[step][2] <= H) {
    		// 选这级速度，然后选下级速度
    		dfs_v1(map, H, D, sumtime + map[step][3], sumergy + map[step][2], step + 1, count + 1, mintime);
    
    		// 选这级速度，然后继续选择同级速度
    		dfs_v1(map, H, D, sumtime + map[step][3], sumergy + map[step][2], step, count + 1, mintime);
    	}
    
    	// 不选这级速度，然后选下级速度
    	dfs_v1(map, H, D, sumtime, sumergy, step + 1, count, mintime);
    
    	return;
    }
    
    int inference(const int map[5][4], const int H, const int D)
    {
    	int ret = 0;
    	int sumtime = 0;
    	int sumergy = 0;
    	int step = 0;
    	int count = 0;
    	int mintime = INT_MAX;
    
    	dfs_v1(map, H, D, sumtime, sumergy, step, count, &mintime);
    
    	cout << "computation: " << computation << endl;
    	cout << "mintime: " << mintime << " second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    		int H = 0, D = 0; // energy - distance
    		int map[5][4] = { 0 };
    		computation = 0;
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    		}
    
    		ret = inference(map, H, D);
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    computation: 8712216
    mintime: 9200 second
    CASE #1 = 153 20
    computation: 8712216
    mintime: 9200 second
    CASE #2 = 153 20
    
    End of the program, end = 294
    End of the program, end = 294
    Total time taken by CPU: 0.294000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]

### 2.2 深度优先搜索 (递归) 2 ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    int H = 0;
    int D = 0;
    int map[5][4] = { 0 };
    int mintime = INT_MAX;
    
    void dfs_v2(int sumtime, int sumergy, int step, int count)
    {
    	computation++;
    
    	if (sumergy > H) {
    		return;
    	}
    
    	if (sumtime >= mintime) {
    		return;
    	}
    
    	if (count >= D)
    	{
    		if (sumtime < mintime)
    		{
    			mintime = sumtime;
    		}
    
    		return;
    	}
    
    	if (step >= 5) {
    		return;
    	}
    
    	if (sumergy + map[step][2] <= H) {
    		// 选这级速度，然后选下级速度
    		dfs_v2(sumtime + map[step][3], sumergy + map[step][2], step + 1, count + 1);
    
    		// 选这级速度，然后继续选择同级速度
    		dfs_v2(sumtime + map[step][3], sumergy + map[step][2], step, count + 1);
    	}
    
    	// 不选这级速度，然后选下级速度
    	dfs_v2(sumtime, sumergy, step + 1, count);
    
    	return;
    }
    
    int inference()
    {
    	int ret = 0;
    	int sumtime = 0;
    	int sumergy = 0;
    	int step = 0;
    	int count = 0;
    
    	dfs_v2(sumtime, sumergy, step, count);
    
    	cout << "computation: " << computation << endl;
    	cout << "mintime: " << mintime << " second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    
    		for (int h = 0; h < 5; h++)
    		{
    			map[h][0] = 0;
    			map[h][1] = 0;
    			map[h][2] = 0;
    			map[h][3] = 0;
    		}
    
    		computation = 0;
    		H = 0; // energy
    		D = 0; // distance
    		mintime = INT_MAX;
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    
    			if (map[h][2] * D <= H)
    			{
    				if (map[h][3] < mintime)
    				{
    					mintime = map[h][3];
    				}
    			}
    		}
    
    		mintime = mintime * D;
    
    		ret = inference();
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    computation: 8711646
    mintime: 9200 second
    CASE #1 = 153 20
    computation: 8711646
    mintime: 9200 second
    CASE #2 = 153 20
    
    End of the program, end = 250
    End of the program, end = 250
    Total time taken by CPU: 0.250000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]

## 3. 深度优先搜索 (递归) ##

### 3.1 深度优先搜索 (递归) 1 ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    int H = 0;
    int D = 0;
    int map[5][4] = { 0 };
    int mintime = INT_MAX;
    
    void dfs_vip(int sumtime, int sumergy, int step, int count)
    {
    	if (count > D) {
    		return;
    	}
    
    	if (sumergy > H) {
    		return;
    	}
    
    	if (sumtime >= mintime) {
    		return;
    	}
    
    	if (step >= 5) {
    		if ((D == count) && (sumtime < mintime))
    		{
    			mintime = sumtime;
    		}
    
    		return;
    	}
    
    	if (step != 4) {
    		for (int i = 0; i <= D; i++)
    		{
    			dfs_vip(sumtime + map[step][3] * i, sumergy + map[step][2] * i, step + 1, count + i);
    		}
    	}
    	else
    	{
    		int tmp = D - count;
    		dfs_vip(sumtime + map[step][3] * tmp, sumergy + map[step][2] * tmp, step + 1, count + tmp);
    	}
    
    	return;
    }
    
    int inference()
    {
    	int ret = 0;
    	int sumtime = 0;
    	int sumergy = 0;
    	int step = 0;
    	int count = 0;
    
    	dfs_vip(sumtime, sumergy, step, count);
    
    	cout << "computation: " << computation << endl;
    	cout << "mintime: " << mintime << " second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    
    		for (int h = 0; h < 5; h++)
    		{
    			map[h][0] = 0;
    			map[h][1] = 0;
    			map[h][2] = 0;
    			map[h][3] = 0;
    		}
    
    		computation = 0;
    		H = 0; // energy
    		D = 0; // distance
    		mintime = INT_MAX;
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    
    			if (map[h][2] * D <= H)
    			{
    				if (map[h][3] < mintime)
    				{
    					mintime = map[h][3];
    				}
    			}
    		}
    
    		mintime = mintime * D;
    		//mintime = INT_MAX;
    
    		ret = inference();
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 1
    Start of the program, start = 1
    
    computation: 0
    mintime: 9200 second
    CASE #1 = 153 20
    computation: 0
    mintime: 9200 second
    CASE #2 = 153 20
    
    End of the program, end = 31
    End of the program, end = 31
    Total time taken by CPU: 0.030000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]

### 3.2 深度优先搜索 (递归) 2 ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    int H = 0;
    int D = 0;
    int map[5][4] = { 0 };
    int mintime = INT_MAX;
    
    void dfs_vip(int sumtime, int sumergy, int step, int count)
    {
    	if (count > D) {
    		return;
    	}
    
    	if (sumergy > H) {
    		return;
    	}
    
    	if (sumtime >= mintime) {
    		return;
    	}
    
    	if (step >= 5) {
    		if ((D == count) && (sumtime < mintime))
    		{
    			mintime = sumtime;
    		}
    
    		return;
    	}
    
    	if (step != 4) {
    		for (int i = 0; i <= D; i++)
    		{
    			dfs_vip(sumtime + map[step][3] * i, sumergy + map[step][2] * i, step + 1, count + i);
    		}
    	}
    	else
    	{
    		int tmp = D - count;
    		dfs_vip(sumtime + map[step][3] * tmp, sumergy + map[step][2] * tmp, step + 1, count + tmp);
    	}
    
    	return;
    }
    
    int inference()
    {
    	int ret = 0;
    	int sumtime = 0;
    	int sumergy = 0;
    	int step = 0;
    	int count = 0;
    
    	dfs_vip(sumtime, sumergy, step, count);
    
    	cout << "computation: " << computation << endl;
    	cout << "mintime: " << mintime << " second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    
    		for (int h = 0; h < 5; h++)
    		{
    			map[h][0] = 0;
    			map[h][1] = 0;
    			map[h][2] = 0;
    			map[h][3] = 0;
    		}
    
    		computation = 0;
    		H = 0; // energy
    		D = 0; // distance
    		mintime = INT_MAX;
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    		}
    
    		mintime = INT_MAX;
    
    		ret = inference();
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 1
    Start of the program, start = 1
    
    computation: 0
    mintime: 9200 second
    CASE #1 = 153 20
    computation: 0
    mintime: 9200 second
    CASE #2 = 153 20
    
    End of the program, end = 36
    End of the program, end = 36
    Total time taken by CPU: 0.035000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]

### 3.3 深度优先搜索 (递归) 3 ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    int H = 0;
    int D = 0;
    int map[5][4] = { 0 };
    int mintime = INT_MAX;
    
    void dfs_vip(int sumtime, int sumergy, int step, int count)
    {
    	if (count > D) {
    		return;
    	}
    
    	if (sumergy > H) {
    		return;
    	}
    
    	if (sumtime >= mintime) {
    		return;
    	}
    
    	if (step >= 5) {
    		if ((D == count) && (sumtime < mintime))
    		{
    			mintime = sumtime;
    		}
    
    		return;
    	}
    
    	for (int i = 0; i <= D; i++)
    	{
    		dfs_vip(sumtime + map[step][3] * i, sumergy + map[step][2] * i, step + 1, count + i);
    	}
    
    	return;
    }
    
    int inference()
    {
    	int ret = 0;
    	int sumtime = 0;
    	int sumergy = 0;
    	int step = 0;
    	int count = 0;
    
    	dfs_vip(sumtime, sumergy, step, count);
    
    	cout << "computation: " << computation << endl;
    	cout << "mintime: " << mintime << " second" << endl; // 153 min 20 sec = 9200
    
    	ret = mintime;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    
    		for (int h = 0; h < 5; h++)
    		{
    			map[h][0] = 0;
    			map[h][1] = 0;
    			map[h][2] = 0;
    			map[h][3] = 0;
    		}
    
    		computation = 0;
    		H = 0; // energy
    		D = 0; // distance
    		mintime = INT_MAX;
    
    		cin >> H >> D;
    
    		for (int h = 0; h < 5; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2];
    			map[h][3] = map[h][0] * 60 + map[h][1];
    		}
    
    		mintime = INT_MAX;
    
    		ret = inference();
    
    		int minute = 0, second = 0;
    		minute = (int)(ret / 60);
    		second = ret % 60;
    
    		cout << "CASE #" << i << " = " << minute << " " << second << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    computation: 0
    mintime: 9200 second
    CASE #1 = 153 20
    computation: 0
    mintime: 9200 second
    CASE #2 = 153 20
    
    End of the program, end = 107
    End of the program, end = 107
    Total time taken by CPU: 0.107000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200529222500532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200529222102763.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200603003604374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200615231056888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200616001345346.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200616235253884.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20200616235518713.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/20200617000210874.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center