P1005 （C++代码）简单的01背包问题（递归 + 记忆化搜索）

解题思路:简单的01背包问题

注意事项:借此题重新温习了一下01背包问题，用到记忆化搜索

递归版便于理解，理解之后想要更加精简的写法可以看看我的循环版

参考代码:

#include <iostream>

#include <algorithm>

using namespace std;

int t, m;

int arr[101], v[101];

int dp[101][1001];

int rec(int i, int j)

{

if (dp[i][j] >= 0)return dp[i][j];

int res;

if (i == m)res = 0;

else if (j < arr[i])res = rec(i + 1, j);

else res = max(rec(i + 1, j), rec(i + 1, j - arr[i]) + v[i]);

return dp[i][j] = res;

}

int main()

{

fill(dp[0], dp[0] + 101 * 1001, -1);

cin >> t >> m;

for (int i = 0; i < m; ++i)

{

cin >> arr[i] >> v[i];

}

cout << rec(0, t) << endl;

return 0;

}