0/1背包问题回溯法求解

爱玩游戏的Tom
Tom很喜欢玩游戏，他在电脑上下了《GTA5》和《微软飞行模拟》，对于后者他还丧心病狂的下载了所有地图包，导致他可用空间只有mGB，但他还有几个学校要求安装的软件没有下载，他不能全部放下去，因此只能选择性的安装一部分。现在，我们知道每个学习软件的大小以及该学习软件的重要程度，现在Tom找到你，应该安装哪一些软件，使得这些软件的重要程度之和最大。对于输入第一行有n（0 < n <= 100）和m(0 < m <= 1000)两个整数组成，n代表接下来的输入行数，m代表可用空间还剩mGB。接下来的n行，每行两个整数，前一个整数为每个学习软件的大小（GB），后一个整数代表重要程度。对于输出，只有一行，即为最大重要程度之和。
样例
Input：
3 23
15 9
20 5
7 7
Output：
16
下面我们来切掉这道裸题：首先我们定义一个函数，名字索性为dfs。
组成：int dfs(int i,int j)
解释：参数i表示一共有多少件物品，体现在本题中便是多少个软件。参数j则表示电脑还剩的空间（GB）。
dfs(i,j)的返回值所代表的意思便是，一共i个软件，在电脑内存还剩jGB的情况下最大的重要程度。
经过上面的定义，我们显然可以得到？


就上面的问题，我们留意前面dfs的定义，不难得出对于0个软件，不管我们电脑还剩多少内存，它对于我们来说重要程度都为0，因为根本就没有软件。
这就是边界（i==0），同时也是终止条件。
我们在回过头看上面的程序。很遗憾，如果写成这样，当数据规模为最大，即当n=100的时候，程序无法在1秒内得出答案，最后超时，不予通过。指数级的时间复杂度太高了，需要降（一个状态可能会被计算多次）。
如何去降？
对于回溯，降低时间复杂度的有效方式是减枝，前面我们说过，一个状态可能会被计算多次，那么我们便想方设法让他只计算一次。