练习题 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; }