首页 > 分享 > 宠物小精灵之收服【暴搜+DP+代码注释+详细思路=包掌握】

宠物小精灵之收服【暴搜+DP+代码注释+详细思路=包掌握】

萌宠菠菠乐园
2024-12-13 23:43

暴搜：

递归搜索所有的选法的取值。
定义递归函数dfs(u,cnt,s)，表示当前搜索到第u个小精灵，已经收服了cnt个小精灵，皮卡丘当前的体力为s。

对于当前这个小精灵，有两种选择：收服或离开。

如果选择收服，那么精灵球数量会减少，皮卡丘的体力也会减少，同时收服的小精灵数量加1。

如果选择离开，那么精灵球数量不变，皮卡丘的体力也不会减少，但是小精灵数量不会增加。

递归边界为：当精灵球数量为0或者皮卡丘体力小于等于0时，递归结束。

每次递归时，更新答案C和R，并尝试收服下一个小精灵（即dfs(u+1,cnt+1,s-hp)）或者离开下一个小精灵（即dfs(u+1,cnt,s)）。

每个小精灵的收服或离开都可以看做是一个状态，因此可以用递归搜索进行枚举，求得最终的答案。

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 25; int n, m, k; int w[N], t[N]; int ans, res; // dfs(u, cnt, rest): u 表示当前考虑的小精灵编号，cnt 表示已经收服的小精灵数量，rest 表示皮卡丘剩余的体力值。 void dfs(int u, int cnt, int rest) { if (u == k) // 边界情况，搜索到小精灵数量的最大值，退出递归 { if (cnt > ans) // 如果当前收服的小精灵数量比已经搜索到的最大值还大，更新答案 { ans = cnt; res = rest; // 更新皮卡丘的剩余体力值 } else if (cnt == ans) // 如果当前收服的小精灵数量等于已经搜索到的最大值，比较皮卡丘的剩余体力值，更新更大的那个 { res = max(res, rest); } return; } if (rest <= 0) return; // 如果皮卡丘已经没有体力了，返回 dfs(u + 1, cnt, rest); // 不捕捉当前小精灵，直接搜索下一个小精灵 if (w[u] <= n) dfs(u + 1, cnt + 1, rest - t[u]); // 捕捉当前小精灵，更新收服小精灵的数量和皮卡丘的体力值 } int main() { cin >> n >> m >> k; for (int i = 0; i < k; i ++ ) cin >> w[i] >> t[i]; dfs(0, 0, m); // 从第一个小精灵开始搜索，当前还没有收服任何小精灵，皮卡丘还有 m 点体力。 cout << ans << " " << m - res << endl; // 输出最大收服小精灵数量和此时皮卡丘的剩余体力值 return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647

DP：

揭露题目本质：

精灵球个数 - 背包的体积；
皮卡丘的血槽 - 背包的重量；
抓一只野生精灵的精灵球数 - 花费1；
抓一只野生精灵的所受伤害 - 花费2；
价值：可以收服的小精灵的数量，每只小精灵的价值为 1。由于存在两个花费，所以可知这是一个二维费用背包问题！直接开始设方程：f[i][j][k]；
状态表示：
f[i][j][k]：表示从前 i 件物品里面选，花费1不超过 j，花费2不超过 k 的选法里面所选精灵数量最大的选法！
状态更新：
考虑当前第 i 个物品：可以选和不选两种情况：
1.不选：f[i-1][j][k]，则从前 i - 1件物品里面选，花费1和花费2不超过 j 和 k 的选法的最大值（继承思想）。
2.选：f[i-1][j-v[i]][k-w[i]] + 1；选第 i 个精灵所以数量+1，然后利用余额从前 i-1 件里面选取最大数量的精灵个数。注意：题目中说了一旦皮卡丘的体力值是小于等于0的时候，就需要停止了，并且当前使得皮卡丘爆0的那只小精灵，也不会被收复，比如说皮卡丘血槽为 10，一只小精灵的伤害也是10，那么收复这只小精灵的话，则最后体力为0，则小精灵也不会被收复。所以说体力值为10的话，10伤害的精灵不能收复，而我们的递推式表示的是10伤害的也能选取，所以说只能从10-1开始！最后的while循环指的是：我们在求取了花费2（皮卡丘体力值）不超过 m-1的情况下所能捕获精灵的最大数量。那么我们想知道花费 m-2 能否捕获那么多精灵，m-3呢？m-4呢？所以说是逆推。使得在满足捕获的最大精灵数量不变的情况下花费2最小！

#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e3+10, M = 5e2+10, K = 1e2 + 10; int f[N][M]; //表示从前i件物品里面选，花费一不超过j，花费2不超过k的选法的最大价值。 int n, m, k; int main() { cin >> n >> m >> k; for (int i=0; i < k; i ++) //k只小精灵！ { int v1, v2, w; cin >> v1 >> v2; //花费1和花费2！ for (int j=n; j >= v1; j --) //倒推！ { for (int p=m-1; p>=v2; p--) { f[j][p] = max(f[j][p], f[j-v1][p-v2] + 1); } } } cout << f[n][m-1] << " "; int res=m-1; //求最大数量不变的情况下，皮卡丘的体力值的最大可以保留多少! while (res > 0 && f[n][res-1] == f[n][m-1]) res --; cout << m - res << endl; return 0; }

123456789101112131415161718192021222324252627282930313233343536