2023年8月1日发(作者：)

01背包问题递归c语⾔程序,P1005（C++代码）简单的01背包问题（递归+记忆化搜索）...解题思路:简单的01背包问题注意事项:借此题重新温习了⼀下01背包问题，⽤到记忆化搜索递归版便于理解，理解之后想要更加精简的写法可以看看我的循环版参考代码:#include#includeusing 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;}

2023年8月1日发(作者：)

01背包问题递归c语⾔程序,P1005（C++代码）简单的01背包问题（递归+记忆化搜索）...解题思路:简单的01背包问题注意事项:借此题重新温习了⼀下01背包问题，⽤到记忆化搜索递归版便于理解，理解之后想要更加精简的写法可以看看我的循环版参考代码:#include#includeusing 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;}