---
title: "宠物小精灵之收服"
created: 2025-11-28
tags:
  - 算法
---

# 宠物小精灵之收服

## 题目 [宠物小精灵之收服](https://www.acwing.com/solution/content/210965/)

![[image-9f641c73.png]]

![[image-a2f2a217.png]]

![[image-2cc71617.png]]

## 思路分析

![[image-5df55958.png]]

加了一个维度限制的背包问题

要在k个精灵中选 有精灵球数量N和皮卡丘的体力M作为限制 要求得到的精灵数最多 若有相同情况 取剩余M更大的那个

![[image-5df55958.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,M=510,K=110;

int num[K],cost[N];

int f[N][M];

int main()

{

    int V1,V2,n;

    cin>>V1>>V2>>n;

    for(int i=1;i<=n;i++)

    {

        int v1,v2;

        cin>>v1>>v2;

        for(int j=V1;j>=v1;j--){

            for(int k=V2;k>=v2;k--){

                f[j][k]=max(f[j][k],f[j-v1][k-v2]+1);

            }

        }

    }

    cout<<f[V1][V2]<<" ";

    int k=V2;

    //反推得到最小体力消耗且达到最大值的

    while (k >= 0 && f[V1][k] == f[V1][V2])

        k--;

    cout<<V2-k-1;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[加维度背包问题练习|加维度背包问题练习]] 🏠 [[00-刷题理模型]] ➡️ [[有依赖+多重（未解决）金明的预算方案|有依赖+多重（未解决）金明的预算方案]]