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