解题思路:动态规划 + 循环
注意事项:进一步对递归进行优化
参考代码:
#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; }
0.0分
0 人评分