首页 > 分享 > [01背包] 宠物小精灵之收服(01背包+二维费用背包+思维)

[01背包] 宠物小精灵之收服(01背包+二维费用背包+思维)

萌宠菠菠乐园
2024-12-16 18:27

文章目录 0. 前言1. 01背包裸题

0. 前言

相关：

[背包] 背包问题算法模板(模板)

1. 01背包裸题

1022. 宠物小精灵之收服

在这里插入图片描述

每个精灵仅被收服一次，故可以考虑 01 背包，是典型二维费用套 01 背包裸题。

思路：

在此有两个花费和一个价值 花费1：精灵球数量花费2：皮卡丘体力值价值：已收服小精灵的数量。每个小精灵价值为 1 状态表示： f[i,j,k]：所有只从前 i 个精灵中选，且花费 1 不超过 j，花费 2 不超过 k 的最大收服精灵数目 状态计算： 和 01 背包一致，根据最后一步第 i 个物品选还是不选分类f[i,j,k] = max(f[i - 1,j,k],f[i-1,j-v1[i],k-v2[i]]+1)优化至二维：f[j][k] = max(f[j][k],f[j-v1[i]][k-v2[i]]+1)。但需要注意枚举 j、k 的时候需要逆序枚举，本质还是 01 背包问题 答案： 最多收服的小精灵数量：f[K,N,M]最少耗费体力，从 K-1 开始枚举到 0，找到收服数量为 f[K,N,M] 的最小值 k，f[K,N,t]==f[K,N,M]题目要求：使得皮卡丘体力小于等于 0 的野生小精灵也不会被收服，，所以皮卡丘的体力需要从 V2-1 开始

01 背包二维费用，优化掉 i，三维变两维，体积从大到小进行枚举。

代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 1005, M = 505, K = 105; int n, m, t; int f[N][M]; int main() { cin >> n >> m >> t; for (int i = 0; i < t; ++i) { int a, b; cin >> a >> b; for (int j = n; j >= a; --j) for (int k = m - 1; k >= b; --k) f[j][k] = max(f[j][k], f[j - a][k - b] + 1); } cout << f[n][m - 1] << ' '; int k = m - 1; while (k > 0 && f[n][k - 1] == f[n][m - 1]) k --; cout << m - k << endl; return 0; }

12345678910111213141516171819202122232425

来自大佬优化：1022. 宠物小精灵之收服体积与价值选择问题效率对比

在背包问题中，体积 w 与价值 v 是可以互逆的可以将 f[i] 表示为体积为 i 能装的最大价值，也可以将 f[i] 表示为价值为 i 所需的最小体积。两者等价，只需要选择范围较小的那维作为体积就可以了！这直接影响到时空复杂度。这题就是个案例。

上面是以体力、精灵球数为费用、精灵数为价值， O ( n m k ) O(nmk) O(nmk) f[i][j] 表示为体力为 i，精灵球数为 j 所收集到的最大精灵。

差不多是 5e7 的计算量。

本题 k 是很小的，所有可以以体力、精灵数为费用，精灵球数为代价，则为 O ( k 2 m ) O(k^2m) O(k2m)

f[i][j] 表示体力为 i，收集了 j 个精灵，且使用最小的精灵球数量。

差不多是 5e6 的计算量。优化了 10 倍。

在这里插入图片描述

优化代码

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1005, M = 505, K = 105; const int INF = 0x3f3f3f3f; int n, m, t; int f[M][K]; int main() { cin >> n >> m >> t; memset(f, 0x3f, sizeof f); for (int i = 0; i < t; ++i) f[i][0] = 0; // 不收服精灵,则不用精灵球,故初始化为0 for (int i = 0; i < t; ++i) { int a, b; cin >> a >> b; for (int j = m; j >= b; --j) for (int k = t; k >= 1; --k) if (f[j - b][k - 1] + a <= n) f[j][k] = min(f[j][k], f[j - b][k - 1] + a); } for (int k = t; k >= 0; --k) { // 逆序枚举精灵最大只数 int p = INF; for (int j = 0; j < m; ++j) // 体积从0~m-1,顺序枚举 if (f[j][k] != INF && j < p)// 若发生转移且体积有更新,则获得最小体积下的最大收服精灵数 p = j; if (p != INF) { cout << k << ' ' << m - p << endl; return 0; } } return 0; }

12345678910111213141516171819202122232425262728293031323334353637