P1005 （C++代码）简单的01背包问题（循环 + 动态规划）比递归更加快更加简短

解题思路:动态规划 + 循环

注意事项:进一步对递归进行优化

参考代码:

#include <iostream>
using namespace std;

int t, m;
int arr[101], v[101];
int dp[101][1001];

int main()
{
cin >> t >> m;
for (int i = 0; i < m; ++i)
{
cin >> arr[i] >> v[i];
}
for (int i = m - 1; i >= 0; --i)
{
for (int j = 0; j <= t; ++j)
{
if (j < arr[i])dp[i][j] = dp[i + 1][j];
else dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - arr[i]] + v[i]);
}
}
cout << dp[0][t] << endl;
return 0;
}