C++---背包模型---收服精灵（每日一道算法2023.3.11）

注意事项：
本题是"动态规划—01背包"的扩展题，优化的思路不多赘述，dp思路会稍有不同，下面详细讲解。
本题偏向阅读理解，给每种变量归类起名字很有帮助哦。
切记先看思路，再看代码。（大佬当我没说）

题目：
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入格式
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出格式
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

数据范围
0<N≤1000,
0<M≤500,
0<K≤100

输入:
10 100 5
7 10
2 40
2 50
1 20
4 20

输出：
3 30

#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1010, M = 510;
int n, v1, v2;      //n代表精灵总数量，v1是精灵球总数量看作为体积，v2是皮卡丘总体力也看作为体积
int a[N], b[N];     //a[i],b[i]分别代表对于精灵i，所需要的精灵球数量，和需要消耗的皮卡丘体力值
int f[N][M];int main () {//读入cin >> v1 >> v2 >> n;for (int i = 1; i<=n; i++) cin >> a[i] >> b[i];//01背包dp的修改版，分别枚举物品，花费1，花费2for (int i = 1; i<=n; i++) {for (int j = v1; j>=a[i]; j--) {        //从上一维i-1转移过来，从大到小枚举，并且省去了判断for (int k = v2-1; k>=b[i]; k--) {f[j][k] = max(f[j][k], f[j-a[i]][k-b[i]] + 1);}}}//第一个输出的t1是：在花费1小于等于v1同时花费2小于等于v2-1时，最大价值为多少（注意，是v2-1而不是v2，因为题目中说"使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服",所以至少要剩余一点体力）//第二个输出的t2是：在最大价值等于t1时，皮卡丘最少需要花费多少体力，然后用v2最大体力减去最少花费体力t2，即为最多剩余体力int t1 = f[v1][v2-1], t2 = 0x3f3f3f;for (int k = 0; k<=v2-1; k++) {if (f[v1][k] == t1) t2 = min(t2, k);}cout << t1 << " " << v2-t2;
}

思路：
经典的y式dp法

下面将精灵球花费简写为花费1，将皮卡丘体力花费简写为花费2。
a[i]代表第i个精灵的精灵球花费，b[i]代表第i个精灵的皮卡丘体力花费。

1.状态表示
f[i][j][k]：考虑前i个精灵，花费1不超过j，花费2不超过k时的所有方案，属性为Max。

2.状态计算
状态计算部分和01背包很类似，不如说所有背包问题都很类似。
以 选择/不选择 第i个精灵为划分，
1.当不选择第i个精灵时:
f[i][j][k] = f[i-1][j][k]
2.当选择第二个精灵时:
f[i][j][k] = max(f[i][j][k], f[i-1][j-a[i]][k-b[i]] + 1)

这里还要注意一个问题，就是计算花费2时，题目中明确说明了"使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服"也就说明，我们只能计算到皮卡丘总体力值-1。

同时由于我们无法开三维数组，那么就将第i维也就是物品维度优化即可，参考01背包的优化方式。

声明：
算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流