【c++】大疆笔试题，动态规划模板类解决0/1背包问题_大疆动态规划

题目如下：

爱玩游戏的小N
时间限制:C/C++语言1000MS;其他语言3000MS 内存限制:C/C++语言65536KB;其他语言589824KB
题目描述
有许多程序员都热爱玩游戏,而小n自称为游戏王,曾玩过几百种游戏,几乎所有能玩到的游戏大作都玩遍了。随着时间的推移,他发觉已经没有游戏可以让他玩了!于是他想改玩一些古老的游戏,以成为真正的游戏王。他希望在接下来的一段时间内将过去出的游戏全部玩一遍,但是毕竟时间有限,因此他感到很苦恼。于是他给每个游戏标上一个成就值,同时估算了完成这些游戏所需要的时间。现在他只有X天时间。而每个游戏一旦开始玩,至少需要玩一天才能够停下来。那么,他所玩完的游戏的成就值之和最大能达到多少呢?(每个游戏必须玩完才能取得成就值。
输入
第一行输入case数T(0<T<20)。对于每个case,第一行输入游戏的数目N（0<N<11),总时间X(0<x<1000)空格分隔。从第二行到第N+1行每行输入游戏的成就值Ai(0<Ai<10000)需要花费时间Bi(0<Bi<10000)
输出 对每个case输出一行,成就值之和的最大值。

这明显是个0/1背包问题，考虑到时间限制与内存限制，暴力穷举解法不太合适，因此采用动态规划求解。动态规划的理论与思想网上很多，这里不再赘述，直接上代码：
其实这个代码用了模板类，实现的是任意数字输入类型的0/1背包问题，也就是背包的容量和物品的价值、容量都可以是int float double等数字数据类型中的任意一种，比题目要求的功能更多了些。
structs.h

#pragma once
/*
输入：
1.case数case_num，0~20
对于每个case，1.输入游戏数目game_num,0~11,总时间t,0~1000
			2~n+1.游戏成就值game_val,0~10000，游戏耗时game_time,0~10000
输出：
每个case输出一行，成就值之和的最大值
*/

#include <iostream>
#include <vector>
#include "utls.h"

//宏定义价值与时间的数据类型
typedef double value_type;
typedef double time_type;

using namespace std;

//游戏结构体
struct game_struct
{
   
	int game_num;//游戏个数
	time_type total_time;//总时间
	vector<value_type> values;//游戏价值队列
	vector<time_type> times;//游戏耗时列
};

//输入数据结构体
struct input_data_struct
{
   
	int case_num;//case数
	vector<game_struct> games;//游戏结构体队列
	//初始化输入数据
	input_data_struct() {
   
		//输入case数并检查数值范围
		cout << "case_num:" << endl;
		cin >> case_num;
		utls::check_num_range<int>(case_num, 0, 20);
		//遍历每个case
		for (int i = 0; i < case_num; i++) {
   
			//当前游戏结构体
			game_struct game;
			//输入游戏数量与总时间，并检查数值范围
			cout << "game number and total time:" << endl;
			cin >> game.game_num >> game.total_time;
			utls::check_num_range<int>(game.game_num, 0, 11);
			utls::check_num_range<time_type>(game.total_time, 0, 1000);
			//再次循环，按照游戏数遍历，输入每个游戏的value与time
			for (int i = 0; i < game.game_num; i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54