开心的金明 （C++代码）

解题思路:
        我们从最后一个物品开始考虑，有选和不选两种选项，当然需要满足条件：

total >= value[num]

即我们总的金钱需要能够买得起该物品，当我们选择买，状态就变成了：

OPT(total - value[num], num - 1) + weigth[num] * value[num]

我们的钱少了相应的值，增加了某个值，这个值就是题目所求的值，那么我们选不买的时候：

OPT(total, num - 1)

钱的数量没有改变，跳到下一个物品，而这两条方程就叫做状态转移方程。

        那么是递归，我们就要考虑递归出口。

    1. 当我们买不起的时候，我们没得选，只能移向下一个物品：

OPT(total, num - 1)

但当这个物品是最后一个物品的时候，我们买不了，所以返回的是 0；

    2. 当我们能买当前物品，但该物品已经是最后一个了，我们就不需要考虑状态转移方程了，那么出口返回：

 weigth[num] * value[num]（ weigth[0] * value[0]）

        有了关系式子，又有了递归出口，那么整个递归就完成了。但有时候物品太多的时候递归就会 TLE，这时候就有了动态规划，核心也是状态转移方程。

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int value[N], weigth[N];

int OPT(int total, int num) {
	if (total < value[num]) {
		if (num > 0)
			return OPT(total, num - 1);
		else
			return 0;
	}
	if (num == 0)
		return weigth[num] * value[num];

	if (total >= value[num]) {
		int A = OPT(total - value[num], num - 1) + weigth[num] * value[num];
		int B = OPT(total, num - 1);
		return A > B ? A : B;
	}
}

int main() {
	int total, num;
	cin >> total >> num;
	for (int i = 0; i < num; i++)
		cin >> value[i] >> weigth[i];
	cout << OPT(total, num - 1);
	return 0;
}