解题思路:简单的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;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:718 |
A+B for Input-Output Practice (C++代码)浏览:608 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:750 |
printf基础练习2 (C语言代码)浏览:741 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:507 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:1329 |
罗列完美数 (C语言代码)浏览:491 |
局部变量作函数返回值的问题浏览:976 |
GC的苦恼 (C语言代码)浏览:621 |
整数平均值 (C语言代码)浏览:782 |