首页分享宠物小精灵收服策略：01背包算法与体力优化

宠物小精灵收服策略：01背包算法与体力优化

来源：萌宠菠菠乐园时间：2024-12-19 05:07

宠物小精灵之收服

题目描述

核心思路

从题干中抽取"收服野生小精灵需要花费精灵球"和"收服野生小精灵需要花费皮卡丘的体力值"，这是两个约束条件，每次只允许用一个精灵球来收服一个野生小精灵，因此这是一道二维费用01背包问题。

第一维表示收服野生小精灵所需要花费精灵球的数量，第二维表示收服野生小精灵所需要花费皮卡丘的体力值

体积1：精灵球数量体积2：皮卡丘体力价值：小精灵数量

状态表示：f[i][j][k]表示只从前i个物品中选，体积1不超过j，体积2不超过k的选法集合的最大价值

状态计算： f [ i ] [ j ] [ k ] = m a x ( f [ i − 1 ] [ j ] [ k ] , f [ i − 1 ] [ j − v 1 [ i ] ] [ k − v 2 [ i ] ] + 1 ) f[i][j][k] = max(f[i - 1][j][k], f[i - 1][j - v1[i]][k - v2[i]] + 1) f[i][j][k]=max(f[i−1][j][k],f[i−1][j−v1[i]][k−v2[i]]+1)

注意：使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服，设皮卡丘的最大体力为 x x x，那么不可能用到 x x x，至少得留下一个体力吧(题意描述的)，因此最多用到的体力值是 x − 1 x-1 x−1而不是 x x x

那么最多收服野生小精灵的数量为 f [ K ] [ N ] [ M − 1 ] f[K][N][M-1] f[K][N][M−1]

那么我们该如何求出剩余的最大体力值呢？

我们可以先考虑收服这么多野生小精灵受到的最小伤害是 f [ K ] [ N ] [ m ] = f [ K ] [ N ] [ M − 1 ] f[K][N][m]=f[K][N][M-1] f[K][N][m]=f[K][N][M−1]，其中 m m m可取0,1,2…,M-1，那么剩余的最大体力就是 M − m M-m M−m。

注意： f [ K ] [ N ] [ ] f[K][N][] f[K][N][]数组一定是单调递增的，即精灵球数量一致时，皮卡丘体力用的越多收服的精灵也一定越多，因此我们可以正序或逆序去扫描一遍 f [ K ] [ N ] [ ] f[K][N][] f[K][N][]，找到值等于最优解的 f [ K ] [ N ] [ M − 1 ] f[K][N][M - 1] f[K][N][M−1]的最小体力 k k k，那么此时的 k k k含义就是收服这些野生小精灵消耗的最少体力值，那么剩余的最大体力值就是 M − k M-k M−k

参考01背包可以把二维数组优化为一维数组，这里也可以进行优化。

问题：为什么是k>0&& f [ m 1 ] [ k − 1 ] = = f [ m 1 ] [ m 2 − 1 ] f[m1][k-1]==f[m1][m2-1] f[m1][k−1]==f[m1][m2−1]呢？

首先 k > 0 k>0 k>0，是因为题目说了皮卡丘的体力不能为0，至少要有1血。然后 f [ m 1 ] [ m 2 − 1 ] f[m1][m2-1] f[m1][m2−1]是我们求出来的能够收服的最多野生小精灵的数量。这里为什么是 f [ m 1 ] [ k − 1 ] f[m1][k-1] f[m1][k−1]而不是 f [ m 1 ] [ k ] f[m1][k] f[m1][k]主要是因为比如 f f f值有1 3 5 6 6 6 ，如果写成 f [ m 1 ] [ k ] f[m1][k] f[m1][k]，那么最终 k k k停在了值为5的地方，但是使用 f [ m 1 ] [ k − 1 ] f[m1][k-1] f[m1][k−1]，那么最终 k k k停在了值为 6 6 6的地方，而这个6就是最左侧的，它所对应的体力值就是最小的，正是我们需要的答案。

代码

#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1010,M=510; //f[j][k]表示花费了j个精灵球,花费了k个体力值,所获得的野生小精灵的最大数量 int f[N][M]; //m1表示小智的精灵球数量 m2表示皮卡丘初始的体力值 n表示野生小精灵的数量 int n,m1,m2; int main() { scanf("%d%d%d",&m1,&m2,&n); //把野生小精灵当作物品 for(int i=0;i<n;i++) //枚举物品 { int v1,v2; scanf("%d%d",&v1,&v2); for(int j=m1;j>=v1;j--) //枚举花费1小智的精灵球数量 { for(int k=m2;k>=v2;k--) //枚举花费2皮卡丘的体力值 { f[j][k]=max(f[j][k],f[j-v1][k-v2]+1); } } } //由于使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服 //因此皮卡丘的体力值不可能用到最大m2 最多就用到体力m2-1 至少得剩下1血吧 //最多收服f[m1][m2-1]个野生小精灵 printf("%d ",f[m1][m2-1]); int k=m2-1; //找到那些价值等于f[m1][m2-1]的花费体力值最小的那个 while(k>0&&f[m1][k-1]==f[m1][m2-1]) k--; //上面的k求出来的是消耗的最少体力值是k //那么剩余体力值最多为m2-k printf("%dn",m2-k); return 0; } 123456789101112131415161718192021222324252627282930313233343536373839