练习题 No.5 背包问题(动态规划-记忆化搜索)

要求

有n个背包和价值分为 wi , vi 的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

限制条件

• (1 <= n <= 100)
• (1 <= wi , vi <= 100)
• (1 <= W <= 10000)

输入格式

第一行输入n
接下来n行的物品（w,v）
最后输入一行w

输出格式

输出一行价值总和的最大值

测试输入

4
2 3
1 2
3 4
2 2
5

测试输出

7

解题思路

利用函数参数一定，返回值一定，剪枝掉重复运算的部分。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1001][1001];
int n;
int w;
pair<int, int> bag[1001];
int rec(int i, int j) {
int r;
if (dp[i][j] >= 0) {
return dp[i][j];
}
if (i == n) {
r = 0;
} else if (j < bag[i].first) {
r = rec(i + 1, j);
} else {
r = max(rec(i + 1, j), rec(i + 1, j - bag[i].first) + bag[i].second);
}
dp[i][j] = r;
return r;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> bag[i].first >> bag[i].second;
}
cin >> w;
memset(dp, -1, sizeof(dp));
cout << rec(0, w);
return 0;
}

最后

以上就是从容夏天为你收集整理的练习题 No.5 背包问题(动态规划-记忆化搜索)的全部内容，希望文章能够帮你解决练习题 No.5 背包问题(动态规划-记忆化搜索)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。